Goncharov, S;
Milius, S;
Silva, A;
(2020)
Toward a Uniform Theory of Effectful State Machines.
ACM Transactions on Computational Logic
, 21
(3)
, Article 23. 10.1145/3372880.
Preview |
Text
1401.5277v5 (1).pdf - Accepted Version Download (791kB) | Preview |
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.
| Type: | Article |
|---|---|
| Title: | Toward a Uniform Theory of Effectful State Machines |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1145/3372880 |
| Publisher version: | https://doi.org/10.1145/3372880 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| Keywords: | Monads, side-effects, coalgebras, bialgebraic semantics, Kleene theorem |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10117569 |
Archive Staff Only
 |
View Item |
