Residual Nominal Automata

Joshua Moerman, Matteo Sammartino

Research output: Chapter in Book/Report/Conference proceedingConference Article in proceedingAcademicpeer-review

Abstract

We are motivated by the following question: which nominal languages admit an active learning algorithm? This question was left open in previous work, 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.
Original languageEnglish
Title of host publicationCONCUR 2020
Subtitle of host publication31st International Conference on Concurrency Theory
EditorsIgor Konnov, Laura Kovács
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages44:1-44:21
Number of pages21
ISBN (Print)978-3-95977-160-3
DOIs
Publication statusPublished - 2020
Externally publishedYes
Event31st International Conference on Concurrency Theory - Online, Austria
Duration: 1 Sep 20204 Sep 2020
Conference number: 31
http://concur2020.forsyte.at/

Conference

Conference31st International Conference on Concurrency Theory
Abbreviated titleCONCUR 2020
Country/TerritoryAustria
Period1/09/204/09/20
Internet address

Fingerprint

Dive into the research topics of 'Residual Nominal Automata'. Together they form a unique fingerprint.

Cite this