A Kleene theorem for nominal automata
Résumé
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.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...