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.
Complete list of metadatas

https://hal.archives-ouvertes.fr/hal-02112892
Contributor : Paul Brunet <>
Submitted on : Saturday, April 27, 2019 - 11:19:12 AM
Last modification on : Monday, May 6, 2019 - 12:12:02 PM

File

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02112892, version 1

Collections

Citation

Paul Brunet, Alexandra Silva. A Kleene theorem for nominal automata. 2019. ⟨hal-02112892⟩

Share

Metrics

Record views

9

Files downloads

13