Skip to Main content Skip to Navigation
Conference papers

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
Complete list of metadata

Cited literature [31 references]  Display  Hide  Download

https://hal.inria.fr/hal-01402071
Contributor : Hal Ifip <>
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)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

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⟩

Share

Metrics

Record views

240

Files downloads

260