A (co)algebraic theory of succinct automata

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

doi:10.1016/j.jlamp.2019.02.008

A (co)algebraic theory of succinct automata

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

Research output: Contribution to journal › Article › Academic › peer-review

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.

Original language	English
Pages (from-to)	112-125
Number of pages	14
Journal	Journal of Logical and Algebraic Methods in Programming
Volume	105
DOIs	https://doi.org/10.1016/j.jlamp.2019.02.008
Publication status	Published - Jun 2019
Externally published	Yes

Access to Document

10.1016/j.jlamp.2019.02.008

Cite this

@article{76116df7187d4e9ca147059a0467c071,

title = "A (co)algebraic theory of succinct automata",

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.",

author = "Heerdt, \{Gerco van\} and Joshua Moerman and Matteo Sammartino and Alexandra Silva",

note = "DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.",

year = "2019",

month = jun,

doi = "10.1016/j.jlamp.2019.02.008",

language = "English",

volume = "105",

pages = "112--125",

journal = "Journal of Logical and Algebraic Methods in Programming",

issn = "2352-2208",

publisher = "Elsevier Inc.",

}

TY - JOUR

T1 - A (co)algebraic theory of succinct automata

AU - Heerdt, Gerco van

AU - Moerman, Joshua

AU - Sammartino, Matteo

AU - Silva, Alexandra

N1 - DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.

PY - 2019/6

Y1 - 2019/6

N2 - 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.

AB - 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.

U2 - 10.1016/j.jlamp.2019.02.008

DO - 10.1016/j.jlamp.2019.02.008

M3 - Article

SN - 2352-2208

VL - 105

SP - 112

EP - 125

JO - Journal of Logical and Algebraic Methods in Programming

JF - Journal of Logical and Algebraic Methods in Programming

ER -

A (co)algebraic theory of succinct automata

Abstract

Access to Document

Fingerprint

Cite this