Residual Nominal Automata

Joshua Moerman; Matteo Sammartino

doi:10.4230/LIPIcs.CONCUR.2020.44

Residual Nominal Automata

Research output: Chapter in Book/Report/Conference proceeding › Conference Article in proceeding › Academic › peer-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 language	English
Title of host publication	CONCUR 2020
Subtitle of host publication	31st International Conference on Concurrency Theory
Editors	Igor Konnov, Laura Kovács
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages	44:1-44:21
Number of pages	21
ISBN (Electronic)	9783959771603
ISBN (Print)	978-3-95977-160-3
DOIs	https://doi.org/10.4230/LIPIcs.CONCUR.2020.44
Publication status	Published - 1 Aug 2020
Externally published	Yes
Event	31st International Conference on Concurrency Theory - Online, Austria Duration: 1 Sept 2020 → 4 Sept 2020 Conference number: 31 http://concur2020.forsyte.at/

Conference

Conference	31st International Conference on Concurrency Theory
Abbreviated title	CONCUR 2020
Country/Territory	Austria
Period	1/09/20 → 4/09/20
Internet address	http://concur2020.forsyte.at/

Keywords

Closure
Decidability
Derivative language
Exact learning
Lattice theory
Nominal automata
Residual automata

Access to Document

10.4230/LIPIcs.CONCUR.2020.44Licence: CC BY

1 Article

Residuality and Learning for Nondeterministic Nominal Automata
Moerman, J. & Sammartino, M., 3 Feb 2022, In: Logical Methods in Computer Science. 18, 1, 28 p., 29.
Research output: Contribution to journal › Article › Academic › peer-review

Open Access

Cite this

@inproceedings{b30381813d33411a99706b9b3918c776,

title = "Residual Nominal Automata",

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.",

keywords = "Closure, Decidability, Derivative language, Exact learning, Lattice theory, Nominal automata, Residual automata",

author = "Joshua Moerman and Matteo Sammartino",

note = "DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.; 31st International Conference on Concurrency Theory , CONCUR 2020 ; Conference date: 01-09-2020 Through 04-09-2020",

year = "2020",

month = aug,

day = "1",

doi = "10.4230/LIPIcs.CONCUR.2020.44",

language = "English",

isbn = "978-3-95977-160-3",

pages = "44:1--44:21",

editor = "Igor Konnov and Laura Kov{\'a}cs",

booktitle = "CONCUR 2020",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

address = "Germany",

url = "http://concur2020.forsyte.at/",

}

Moerman, J & Sammartino, M 2020, Residual Nominal Automata. in I Konnov & L Kovács (eds), CONCUR 2020: 31st International Conference on Concurrency Theory., 44, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, pp. 44:1-44:21, 31st International Conference on Concurrency Theory , Austria, 1/09/20. https://doi.org/10.4230/LIPIcs.CONCUR.2020.44

Residual Nominal Automata. / Moerman, Joshua; Sammartino, Matteo.
CONCUR 2020: 31st International Conference on Concurrency Theory. ed. / Igor Konnov; Laura Kovács. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2020. p. 44:1-44:21 44.

Research output: Chapter in Book/Report/Conference proceeding › Conference Article in proceeding › Academic › peer-review

TY - GEN

T1 - Residual Nominal Automata

AU - Moerman, Joshua

AU - Sammartino, Matteo

N1 - Conference code: 31

PY - 2020/8/1

Y1 - 2020/8/1

N2 - 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.

AB - 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.

KW - Closure

KW - Decidability

KW - Derivative language

KW - Exact learning

KW - Lattice theory

KW - Nominal automata

KW - Residual automata

U2 - 10.4230/LIPIcs.CONCUR.2020.44

DO - 10.4230/LIPIcs.CONCUR.2020.44

M3 - Conference Article in proceeding

SN - 978-3-95977-160-3

SP - 44:1-44:21

BT - CONCUR 2020

A2 - Konnov, Igor

A2 - Kovács, Laura

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 31st International Conference on Concurrency Theory

Y2 - 1 September 2020 through 4 September 2020

ER -

Residual Nominal Automata

Abstract

Conference

Keywords

Access to Document

Fingerprint

Research output

Residuality and Learning for Nondeterministic Nominal Automata

Cite this