Document Open Access Logo

Residual Nominal Automata

Authors Joshua Moerman , Matteo Sammartino

PDF
Thumbnail PDF

File

LIPIcs.CONCUR.2020.44.pdf
  • Filesize: 0.55 MB
  • 21 pages

Document Identifiers

Author Details

Joshua Moerman
  • RTWH Aachen University, Germany
Matteo Sammartino
  • Royal Holloway University of London, UK
  • University College London, UK

Funding

ERC AdG project 787914 FRAPPANT, EPSRC Standard Grant CLeVer (EP/S028641/1).

Acknowledgements

We would like to thank Gerco van Heerdt for providing examples similar to that of ℒ_r in the context of probabilistic automata. We thank Borja Balle for references on residual probabilistic languages, and Henning Urbat for discussions on nominal lattice theory. Lastly, we thank the reviewers of a previous version of this paper for their interesting questions and suggestions.

Cite As Get BibTex

Joshua Moerman and Matteo Sammartino. Residual Nominal Automata. In 31st International Conference on Concurrency Theory (CONCUR 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 171, pp. 44:1-44:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.CONCUR.2020.44

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Automata over infinite objects
  • Theory of computation → Automated reasoning
Keywords
  • nominal automata
  • residual automata
  • derivative language
  • decidability
  • closure
  • exact learning
  • lattice theory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Dana Angluin. Learning regular sets from queries and counterexamples. Inf. Comput., 75(2):87-106, 1987. Google Scholar
  2. Dana Angluin, Sarah Eisenstat, and Dana Fisman. Learning regular languages via alternating automata. In IJCAI, pages 3308-3314. AAAI Press, 2015. Google Scholar
  3. Sebastian Berndt, Maciej Liśkiewicz, Matthias Lutter, and Rüdiger Reischuk. Learning residual alternating automata. In AAAI, pages 1749-1755, 2017. URL: http://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14748.
  4. Mikołaj Bojańczyk. Slightly Infinite Sets. Draft September 6, 2019, 2019. URL: https://www.mimuw.edu.pl/~bojan/paper/atom-book.
  5. Mikołaj Bojańczyk, Laurent Braud, Bartek Klin, and Slawomir Lasota. Towards nominal computation. In POPL, pages 401-412, 2012. URL: https://doi.org/10.1145/2103656.2103704.
  6. Mikołaj Bojańczyk, Bartek Klin, and Slawomir Lasota. Automata theory in nominal sets. Logical Methods in Computer Science, 10(3), 2014. Google Scholar
  7. Mikołaj Bojańczyk and Szymon Toruńczyk. On computability and tractability for infinite sets. In LICS, pages 145-154. ACM, 2018. Google Scholar
  8. Benedikt Bollig, Peter Habermehl, Carsten Kern, and Martin Leucker. Angluin-style learning of NFA. In IJCAI, pages 1004-1009, 2009. Google Scholar
  9. Benedikt Bollig, Peter Habermehl, Martin Leucker, and Benjamin Monmege. A robust class of data languages and an application to learning. Logical Methods in Computer Science, 10(4), 2014. URL: https://doi.org/10.2168/LMCS-10(4:19)2014.
  10. Thomas Colcombet. Unambiguity in automata theory. In Descriptional Complexity of Formal Systems - 17th International Workshop, DCFS 2015, Waterloo, ON, Canada, June 25-27, 2015. Proceedings, pages 3-18, 2015. URL: https://doi.org/10.1007/978-3-319-19225-3_1.
  11. Brian A. Davey and Hilary A. Priestley. Introduction to Lattices and Order, Second Edition. Cambridge University Press, 2002. URL: https://doi.org/10.1017/CBO9780511809088.
  12. François Denis and Yann Esposito. Learning classes of probabilistic automata. In COLT, volume 3120 of Lecture Notes in Computer Science, pages 124-139. Springer, 2004. Google Scholar
  13. François Denis and Yann Esposito. On rational stochastic languages. Fundam. Inform., 86(1-2):41-77, 2008. Google Scholar
  14. François Denis, Aurélien Lemay, and Alain Terlutte. Residual finite state automata. Fundam. Inform., 51(4):339-368, 2002. Google Scholar
  15. Murdoch James Gabbay and Vincenzo Ciancia. Freshness and name-restriction in sets of traces with names. In FOSSACSs, pages 365-380, 2011. URL: https://doi.org/10.1007/978-3-642-19805-2_25.
  16. Murdoch James Gabbay and Michael Gabbay. Representation and duality of the untyped λ-calculus in nominal lattice and topological semantics, with a proof of topological completeness. Ann. Pure Appl. Logic, 168(3):501-621, 2017. URL: https://doi.org/10.1016/j.apal.2016.10.001.
  17. Murdoch James Gabbay, Tadeusz Litak, and Daniela Petrișan. Stone duality for nominal boolean algebras with N. In CALCO, volume 6859 of Lecture Notes in Computer Science, pages 192-207. Springer, 2011. Google Scholar
  18. Radu Grigore, Dino Distefano, Rasmus Lerchedahl Petersen, and Nikos Tzevelekos. Runtime verification based on register automata. In TACAS, volume 7795 of Lecture Notes in Computer Science, pages 260-276. Springer, 2013. Google Scholar
  19. Falk Howar, Bengt Jonsson, and Frits W. Vaandrager. Combining black-box and white-box techniques for learning register automata. In Computing and Software Science, volume 10000 of Lecture Notes in Computer Science, pages 563-588. Springer, 2019. Google Scholar
  20. Michael Kaminski and Nissim Francez. Finite-memory automata. Theor. Comput. Sci., 134(2):329-363, 1994. Google Scholar
  21. Michael Kaminski and Daniel Zeitlin. Finite-memory automata with non-deterministic reassignment. Int. J. Found. Comput. Sci., 21(5):741-760, 2010. URL: https://doi.org/10.1142/S0129054110007532.
  22. Michael J. Kearns and Umesh V. Vazirani. An Introduction to Computational Learning Theory. MIT Press, 1994. URL: https://mitpress.mit.edu/books/introduction-computational-learning-theory.
  23. Bartek Klin and Michał Szynwelski. SMT solving for functional programming over infinite structures. In MSFP, volume 207 of EPTCS, pages 57-75, 2016. Google Scholar
  24. Eryk Kopczynski and Szymon Toruńczyk. LOIS: syntax and semantics. In POPL, pages 586-598. ACM, 2017. Google Scholar
  25. Dexter Kozen, Konstantinos Mamouras, Daniela Petrișan, and Alexandra Silva. Nominal kleene coalgebra. In ICAL, pages 286-298, 2015. URL: https://doi.org/10.1007/978-3-662-47666-6_23.
  26. Alexander Kurz, Tomoyuki Suzuki, and Emilio Tuosto. On nominal regular languages with binders. In FOSSACS, pages 255-269, 2012. URL: https://doi.org/10.1007/978-3-642-28729-9_17.
  27. Joshua Moerman. Nominal Techniques and Black Box Testing for Automata Learning. PhD thesis, Radboud University, Nijmegen, The Netherlands, 2019. URL: http://hdl.handle.net/2066/204194.
  28. Joshua Moerman, Matteo Sammartino, Alexandra Silva, Bartek Klin, and Michał Szynwelski. Learning nominal automata. In POPL, pages 613-625. ACM, 2017. Google Scholar
  29. Antoine Mottet and Karin Quaas. The containment problem for unambiguous register automata. In STACS, pages 53:1-53:15, 2019. URL: https://doi.org/10.4230/LIPIcs.STACS.2019.53.
  30. Robert S. R. Myers, Jirí Adámek, Stefan Milius, and Henning Urbat. Coalgebraic constructions of canonical nondeterministic automata. Theor. Comput. Sci., 604:81-101, 2015. Google Scholar
  31. Anil Nerode. Linear automaton transformations. Proceedings of the AMS, 9:541– 544, 1958. Google Scholar
  32. Frank Neven, Thomas Schwentick, and Victor Vianu. Finite state machines for strings over infinite alphabets. ACM Trans. Comput. Log., 5(3):403-435, 2004. Google Scholar
  33. Andrew M. Pitts. Nominal sets: Names and symmetry in computer science. Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 2013. Google Scholar
  34. Lutz Schröder, Dexter Kozen, Stefan Milius, and Thorsten Wißmann. Nominal automata with name binding. In FOSSACS, pages 124-142, 2017. URL: https://doi.org/10.1007/978-3-662-54458-7_8.
  35. Frits W. Vaandrager. Model learning. Commun. ACM, 60(2):86-95, 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact