Towards a Coalgebraic Chomsky Hierarchy

Abstract : The Chomsky hierarchy plays a prominent role in the foundations of theoretical computer science relating classes of formal languages of primary importance. In this paper we use recent developments on coalgebraic and monad-based semantics to obtain a generic notion of a $\mathbb{T}$-automaton, where $\mathbb{T}$ is a monad, which allows the uniform study of various notions of machines (e.g. finite state machines, multi-stack machines, Turing machines, weighted automata). We use the generalized powerset construction to define a generic (trace) semantics for $\mathbb{T}$-automata, and we show by numerous examples that it correctly instantiates for some known classes of machines/languages captured by the Chomsky hierarchy. Moreover, our approach provides new generic techniques for studying expressivity power of various machine-based models.
Document type :
Conference papers
Domain :

Cited literature [31 references]

https://hal.inria.fr/hal-01402071
Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Thursday, November 24, 2016 - 11:05:37 AM
Last modification on : Friday, April 10, 2020 - 10:42:22 AM
Long-term archiving on: : Tuesday, March 21, 2017 - 7:07:09 AM

File

978-3-662-44602-7_21_Chapter.p...
Files produced by the author(s)

Citation

Sergey Goncharov, Stefan Milius, Alexandra Silva. Towards a Coalgebraic Chomsky Hierarchy. 8th IFIP International Conference on Theoretical Computer Science (TCS), Sep 2014, Rome, Italy. pp.265-280, ⟨10.1007/978-3-662-44602-7_21⟩. ⟨hal-01402071⟩

Record views