TY - GEN
T1 - Towards a coalgebraic Chomsky hierarchy (extended abstract)
AU - Goncharov, Sergey
AU - Milius, Stefan
AU - Silva, Alexandra
PY - 2014
Y1 - 2014
N2 - 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 double-struck T-automaton, where double-struck 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 double-struck 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.
AB - 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 double-struck T-automaton, where double-struck 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 double-struck 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.
UR - https://www.scopus.com/pages/publications/84906766154
U2 - 10.1007/978-3-662-44602-7_21
DO - 10.1007/978-3-662-44602-7_21
M3 - Conference contribution
AN - SCOPUS:84906766154
SN - 9783662446010
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 265
EP - 280
BT - Theoretical Computer Science - 8th IFIP TC 1/WG 2.2 International Conference, TCS 2014, Proceedings
PB - Springer Verlag
T2 - 8th IFIP TC 1/WG 2.2 International Conference on Theoretical Computer Science, TCS 2014
Y2 - 1 September 2014 through 3 September 2014
ER -