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 | ||
|
Highlights
in Berlin,
September 2018.
|
More | |
|
MFCS
in Krakow,
August 2016.
|
More | |
Related papers | ||
|
Bracket Algebra, a nominal theory of interleaved scopes
(2019)
with Alexandra Silva and Daniela Petrişan. |
More | |
|
A Kleene theorem for nominal automata
(in ICALP 2019)
with Alexandra Silva. |
More | |
| 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. |
More | |