Toward a Uniform Theory of Effectful State Machines - Goncharov, Sergey; Milius, Stefan; Silva, Alexandra (ACM Transactions on Computational Logic, 2020)
Using recent developments in coalgebraic and monad-based semantics, we present a uniform study of various notions of machines, e.g., finite state machines, multi-stack machines, Turing machines, valence automata, and weighted automata. They are instances of Jacobs's notion of a T-automaton, where T is a monad. We show that the generic language semantics for T-automata correctly instantiates the usual language semantics for a number of known classes of machines/languages, including regular, context-free, recursively-enumerable, and various subclasses of context free languages (e.g., deterministic and real-time ones). Moreover, our approach provides new generic techniques for studying the expressivity power of various machine-based models.
CRIS-Team Scopus Importer:2020-06-05
Keywords: bialgebraic semantics; coalgebras; Kleene theorem; Monads; side-effects