Talk "Towards a Coalgebraic Chomsky Hierarchy"

by Sergey Goncharov

Tue, 02 September 2014 at 12:00 pm in Sinaia, Romania

Joint work with: Stefan Milius, Alexandra Silva

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 \emph{$\BBT$-automaton}, where $\BBT$ is a monad, which allows the uniform study of various notions of machines (e.g.~finite state machines, multi-stack machines, Turing machines, \iffull valence automata, \fi weighted automata). We use the \emph{generalized powerset construction} to define a generic (trace) semantics for $\BBT$-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.