On Learning Nominal Automata with Binders

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