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.

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