A Kleene theorem for nominal automata

with Alexandra Silva .

conference paper, in ICALP 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 – that identifies a subclass of expressions denoting exactly egular nominal languages.

@inproceedings{bs19,
    title = "A Kleene theorem for nominal automata",
    author = "{Paul Brunet}, {Alexandra Silva}",
    year = 2019,
    booktitle = "ICALP",
    doi = "10.4230/LIPIcs.ICALP.2019.107"
}

Links

	Permanent link
	Preprint on HAL
	Paper on DROPS - LIPIcs

Related talks
	A Kleene Theorem for Nominal Automata ICALP in Patras, July 2019.	More
	Bracket Algebra Highlights in Berlin, September 2018.	More
	A formal exploration of Nominal Kleene Algebra 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
	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