Joshua Moerman ; Matteo Sammartino - Residuality and Learning for Nondeterministic Nominal Automata

lmcs:7332 - Logical Methods in Computer Science, February 3, 2022, Volume 18, Issue 1 - https://doi.org/10.46298/lmcs-18(1:29)2022
Residuality and Learning for Nondeterministic Nominal AutomataArticle

Authors: Joshua Moerman ORCID; Matteo Sammartino

    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.


    Volume: Volume 18, Issue 1
    Published on: February 3, 2022
    Accepted on: January 17, 2022
    Submitted on: April 7, 2021
    Keywords: Computer Science - Formal Languages and Automata Theory,F.4.3
    Funding:
      Source : OpenAIRE Graph
    • Formal Reasoning About Probabilistic Programs: Breaking New Ground for Automation; Funder: European Commission; Code: 787914

    Consultation statistics

    This page has been seen 1230 times.
    This article's PDF has been downloaded 573 times.