Canonical Automata via Distributive Law Homomorphisms

Stefan Zetzsche
(University College London)
Gerco van Heerdt
(University College London)
Matteo Sammartino
(Royal Holloway, University of London)
Alexandra Silva
(Cornell University)

The classical powerset construction is a standard method converting a non-deterministic automaton into a deterministic one recognising the same language. Recently, the powerset construction has been lifted to a more general framework that converts an automaton with side-effects, given by a monad, into a deterministic automaton accepting the same language. The resulting automaton has additional algebraic properties, both in the state space and transition structure, inherited from the monad. In this paper, we study the reverse construction and present a framework in which a deterministic au- tomaton with additional algebraic structure over a given monad can be converted into an equivalent succinct automaton with side-effects. Apart from recovering examples from the literature, such as the canonical residual finite-state automaton and the átomaton, we discover a new canonical automaton for a regular language by relating the free vector space monad over the two element field to the neighbourhood monad. Finally, we show that every regular language satisfying a suitable property parametric in two monads admits a size-minimal succinct acceptor.

In Ana Sokolova: Proceedings 37th Conference on Mathematical Foundations of Programming Semantics (MFPS 2021), Hybrid: Salzburg, Austria and Online, 30th August - 2nd September, 2021, Electronic Proceedings in Theoretical Computer Science 351, pp. 296–313.
Published: 29th December 2021.

ArXived at: bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to:
For website issues: