Moerman, J;
Sammartino, M;
(2020)
Residual nominal automata.
In:
Proceedings of the 31st International Conference on Concurrency Theory (CONCUR 2020).
(pp. pp. 441-4421).
Leibniz-Zentrum für Informatik, Dagstuhl Publishing
Preview |
Text
LIPIcs-CONCUR-2020-44.pdf - Published Version Download (579kB) | Preview |
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.
| Type: | Proceedings paper |
|---|---|
| Title: | Residual nominal automata |
| Event: | the 31st International Conference on Concurrency Theory (CONCUR 2020) |
| ISBN-13: | 978-3-95977-160-3 |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.4230/LIPIcs.CONCUR.2020.44 |
| Publisher version: | https://doi.org/10.4230/LIPIcs.CONCUR.2020.44 |
| Language: | English |
| Additional information: | © Joshua Moerman and Matteo Sammartino; licensed under Creative Commons License CC-BY (https://creativecommons.org/licenses/by/3.0/legalcode). |
| Keywords: | nominal automata, residual automata, derivative language, decidability, closure, exact learning, lattice theory |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10112015 |
Loading...
Loading...Loading...Loading...Archive Staff Only
 |
View Item |
