A (co)algebraic theory of succinct automata

Gerco van Heerdt, Joshua Moerman, Matteo Sammartino, Alexandra Silva

Research output: Contribution to journalArticleAcademicpeer-review


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.
Original languageEnglish
Pages (from-to)112-125
Number of pages14
JournalJournal of Logical and Algebraic Methods in Programming
Publication statusPublished - Jun 2019
Externally publishedYes


Dive into the research topics of 'A (co)algebraic theory of succinct automata'. Together they form a unique fingerprint.

Cite this