On Learning Nominal Automata with Binders
This work addresses a domain-specific problem in formal language theory for modeling resource-aware computations, representing an incremental advancement.
The authors tackled the problem of learning nominal automata with binders, which extend classical automata to handle alphabets with names, by proposing a generalization of Angluin's L* algorithm and proving its correctness and theoretical complexity.
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.