Residuality and Learning for Nondeterministic Nominal Automata

Logical Methods in Computer Science, vol. Volume 18, Issue 1

Abstract

We are motivated by the following question: which data languages admit an active learning algorithm? This question was left open in previous work by the authors, and is particularly challenging for languages recognised by nondeterministic automata. To answer it, we develop the theory of residual nominal automata, a subclass of nondeterministic nominal automata. We prove that this class has canonical representatives, which can always be constructed via a finite number of observations. This property enables active learning algorithms, and makes up for the fact that residuality -- a semantic property -- is undecidable for nominal automata. Our construction for canonical residual automata is based on a machine-independent characterisation of residual languages, for which we develop new results in nominal lattice theory. Studying residuality in the context of nominal languages is a step towards a better understanding of learnability of automata with some sort of nondeterminism.

Authors 2

1. Joshua Moerman Aachen

   RWTH Aachen University

   Affiliation as printed

   RTWH Aachen University , Germany

   RTWH Aachen University, Germany

2. Matteo Sammartino

   Royal Holloway University of London

   Affiliation as printed

   300 , San Francisco , CA 94105 , USA , or Eisenacher Strasse 2 , 10777 Berlin , Germany

   Royal Holloway University of London , United Kingdom

   Royal Holloway University of London, United Kingdom