{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T07:47:58Z","timestamp":1771573678959,"version":"3.50.1"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2022,2,3]],"date-time":"2022-02-03T00:00:00Z","timestamp":1643846400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000780","name":"European Commission","doi-asserted-by":"crossref","award":["787914"],"award-info":[{"award-number":["787914"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>We are motivated by the following question: which data languages admit an\nactive learning algorithm? This question was left open in previous work by the\nauthors, and is particularly challenging for languages recognised by\nnondeterministic automata. To answer it, we develop the theory of residual\nnominal automata, a subclass of nondeterministic nominal automata. We prove\nthat this class has canonical representatives, which can always be constructed\nvia a finite number of observations. This property enables active learning\nalgorithms, and makes up for the fact that residuality -- a semantic property\n-- is undecidable for nominal automata. Our construction for canonical residual\nautomata is based on a machine-independent characterisation of residual\nlanguages, for which we develop new results in nominal lattice theory. Studying\nresiduality in the context of nominal languages is a step towards a better\nunderstanding of learnability of automata with some sort of nondeterminism.<\/jats:p>","DOI":"10.46298\/lmcs-18(1:29)2022","type":"journal-article","created":{"date-parts":[[2022,2,3]],"date-time":"2022-02-03T19:49:42Z","timestamp":1643917782000},"source":"Crossref","is-referenced-by-count":1,"title":["Residuality and Learning for Nondeterministic Nominal Automata"],"prefix":"10.46298","volume":"Volume 18, Issue 1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9819-8374","authenticated-orcid":false,"given":"Joshua","family":"Moerman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matteo","family":"Sammartino","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2022,2,3]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/9038\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/9038\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:19:46Z","timestamp":1687292386000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/7332"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,3]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-18(1:29)2022","relation":{"has-preprint":[{"id-type":"arxiv","id":"1910.11666v5","asserted-by":"subject"},{"id-type":"arxiv","id":"1910.11666v3","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"1910.11666","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1910.11666","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,3]]},"article-number":"7332"}}