UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Toward a Uniform Theory of Effectful State Machines

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. Green open access

[thumbnail of 1401.5277v5 (1).pdf]
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
Downloads since deposit
44Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item