Abstract

Nominal automata are models for accepting languages over infinite alphabets. In this paper we refine the hierarchy of nondeterministic nominal automata, by developing the theory of residual automata. In particular, we show that they admit canonical minimal representatives, and the universality problem becomes decidable. We also study exact learning of these automata, and settle questions that were left open about their learnability via observations. Finally, we unveil connections with probabilistic automata.

Links

arXiv