Sammartino, M;
Van Heerdt, G;
Silva, A;
Moerman, J;
(2019)
A (co)algebraic theory of succinct automata.
Journal of Logical and Algebraic Methods in Programming
, 105
pp. 112-125.
10.1016/j.jlamp.2019.02.008.
Preview |
Text
Sammartino_A (co)algebraic theory of succinct automata_AAM.pdf - Accepted Version Download (412kB) | Preview |
Abstract
The classical subset construction for non-deterministic automata can be generalized to other side-effects captured by a monad. The key insight is that both the state space of the determinized automaton and its semantics—languages over an alphabet—have a common algebraic structure: they are Eilenberg-Moore algebras for the powersetgen monad. In this paper we study the reverse question to determinization. We will present a construction to associate succinct automata to languages based on different algebraic structures. For instance, for classical regular languages the construction will transform a deterministic automaton into a non-deterministic one, where the states represent the join-irreducibles of the language accepted by a (potentially) larger deterministic automaton. Other examples will yield alternating automata, automata with symmetries, CABA-structured automata, and weighted automata.`
| Type: | Article |
|---|---|
| Title: | A (co)algebraic theory of succinct automata |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1016/j.jlamp.2019.02.008 |
| Publisher version: | https://doi.org/10.1016/j.jlamp.2019.02.008` |
| 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. |
| 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/10074294 |
Archive Staff Only
 |
View Item |
