A Kleene Theorem for Nominal Automata

ICALP in Patras, July 2019
Nominal automata are a widely studied class of automata designed to recognise languages over infinite alphabets. In this paper, we present a Kleene theorem for nominal automata by providing a syntax to denote regular nominal languages. We use regular expressions with explicit binders for creation and destruction of names and pinpoint an exact property of these expressions - namely memory-finiteness - identifying a subclass of expressions denoting exactly regular nominal languages.

Related talks

Bracket Algebra
Highlights in Berlin, September 2018
A formal exploration of Nominal Kleene Algebra
MFCS in Krakow, August 2016

Related papers

Bracket Algebra, a nominal theory of interleaved scopes (2019)
with Alexandra Silva and Daniela Petrişan.
A Kleene theorem for nominal automata (in ICALP 2019)
with Alexandra Silva.
Algebras of relations: from algorithms to formal proofs (in Université de Lyon 2016) More
A formal exploration of nominal Kleene algebra (in MFCS 2016)
with Damien Pous.