Toward a Uniform Theory of Effectful State Machines

Goncharov S, Milius S, Silva A (2020)

Publication Type: Journal article

Publication year: 2020

Journal

ACM Transactions on Computational Logic Association for Computing Machinery (ACM)

Book Volume: 21

Article Number: 23

Journal Issue: 3

DOI: 10.1145/3372880

Abstract

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.

Authors with CRIS profile

Sergey Goncharov Lehrstuhl für Informatik 8 (Theoretische Informatik) Stefan Milius Lehrstuhl für Informatik 8 (Theoretische Informatik)

Involved external institutions

University College London (UCL) GB United Kingdom (GB)

How to cite

APA:

Goncharov, S., Milius, S., & Silva, A. (2020). Toward a Uniform Theory of Effectful State Machines. ACM Transactions on Computational Logic, 21(3). https://dx.doi.org/10.1145/3372880

MLA:

Goncharov, Sergey, Stefan Milius, and Alexandra Silva. "Toward a Uniform Theory of Effectful State Machines." ACM Transactions on Computational Logic 21.3 (2020).

BibTeX: Download