On Learning Nominal Automata with Binders

Yi Xiao
Emilio Tuosto

We investigate a learning algorithm in the context of nominal automata, an extension of classical automata to alphabets featuring names. This class of automata captures nominal regular languages; analogously to the classical language theory, nominal automata have been shown to characterise nominal regular expressions with binders. These formalisms are amenable to abstract modelling resource-aware computations. We propose a learning algorithm on nominal regular languages with binders. Our algorithm generalises Angluin's L* algorithm with respect to nominal regular languages with binders. We show the correctness and study the theoretical complexity of our algorithm.

In Massimo Bartoletti, Ludovic Henrio, Anastasia Mavridou and Alceste Scalas: Proceedings 12th Interaction and Concurrency Experience (ICE 2019), Copenhagen, Denmark, 20-21 June 2019, Electronic Proceedings in Theoretical Computer Science 304, pp. 137–155.
Published: 12th September 2019.

ArXived at: https://dx.doi.org/10.4204/EPTCS.304.9 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org