A Kleene theorem for nominal automata
Abstract
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.
Origin : Files produced by the author(s)
Loading...