Abstract

In this research we consider the problem of inferring a register automaton from observations. This has been done before for deterministic RA, but is still open for nondeterministic RA. To see why nondeterminism is interesting, consider the well-known learning algorithms L* and NL* for respectively deterministic and nondeterministic automata. Although the representation is different, they operate on the same class of languages (i.e., regular languages). This is not the case for RA, where nondeterminism gives a strictly bigger class of languages than determinism. So not only does the representation changes, so does the class of languages. Our contributions are as follows. This is joint work with Matteo Sammartino.

• We consider residual automata for data languages. We show that their languages form a proper subclass of all languages accepted by nondeterministic RA.

• We give a machine-independent characterisation of this class of languages. For this, we also develop some new results in nominal lattice theory.

• We show that for this class of languages, L*-style algorithms exist.

• The natural generalisation of NL* does not always terminate, surprisingly. Fortunately, the algorithm can be fixed to always terminate.

Links

Extended abstract (PDF)
Poster (PDF)
Full paper