Residual Nominal Automata. / Moerman, Joshua; Sammartino, Matteo.

LIPCs. Vol. 2017 Germany : Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2020. p. 44:1-44:21 44.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Published

Standard

Residual Nominal Automata. / Moerman, Joshua; Sammartino, Matteo.

LIPCs. Vol. 2017 Germany : Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2020. p. 44:1-44:21 44.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Harvard

Moerman, J & Sammartino, M 2020, Residual Nominal Automata. in LIPCs. vol. 2017, 44, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Germany, pp. 44:1-44:21, 31st International Conference on Concurrency Theory, 1/09/20. https://doi.org/10.4230/LIPIcs.CONCUR.2020.44

APA

Moerman, J., & Sammartino, M. (2020). Residual Nominal Automata. In LIPCs (Vol. 2017, pp. 44:1-44:21). [44] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.CONCUR.2020.44

Vancouver

Moerman J, Sammartino M. Residual Nominal Automata. In LIPCs. Vol. 2017. Germany: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2020. p. 44:1-44:21. 44 https://doi.org/10.4230/LIPIcs.CONCUR.2020.44

Author

Moerman, Joshua ; Sammartino, Matteo. / Residual Nominal Automata. LIPCs. Vol. 2017 Germany : Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2020. pp. 44:1-44:21

BibTeX

@inproceedings{4de876da8d094cb492b0a41b34aa812b,
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.",
author = "Joshua Moerman and Matteo Sammartino",
year = "2020",
month = aug,
day = "26",
doi = "10.4230/LIPIcs.CONCUR.2020.44",
language = "English",
volume = "2017",
pages = "44:1--44:21",
booktitle = "LIPCs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
note = "31st International Conference on Concurrency Theory, CONCUR ; Conference date: 01-09-2020 Through 04-09-2020",

}

RIS

TY - GEN

T1 - Residual Nominal Automata

AU - Moerman, Joshua

AU - Sammartino, Matteo

PY - 2020/8/26

Y1 - 2020/8/26

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.

U2 - 10.4230/LIPIcs.CONCUR.2020.44

DO - 10.4230/LIPIcs.CONCUR.2020.44

M3 - Conference contribution

VL - 2017

SP - 44:1-44:21

BT - LIPCs

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

CY - Germany

T2 - 31st International Conference on Concurrency Theory

Y2 - 1 September 2020 through 4 September 2020

ER -