Document Open Access Logo

A Kleene Theorem for Nominal Automata (Track B: Automata, Logic, Semantics, and Theory of Programming)

Authors Paul Brunet , Alexandra Silva

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.107.pdf
  • Filesize: 0.57 MB
  • 13 pages

Document Identifiers

Author Details

Paul Brunet
  • University College London, UK
Alexandra Silva
  • University College London, UK

Funding

ERC Starting Grant ProFoundNet (grant code 679127)
  • Brunet, Paul: EPSRC project EP/R006865/1
  • Silva, Alexandra: Leverhulme Prize (PLP-2016-129)

Cite AsGet BibTex

Paul Brunet and Alexandra Silva. A Kleene Theorem for Nominal Automata (Track B: Automata, Logic, Semantics, and Theory of Programming). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 107:1-107:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.107

Abstract

Nominal automata are a widely studied class of automata designed to recognise languages over infinite alphabets. In this paper, we present a Kleene theorem for nominal automata by providing a syntax to denote regular nominal languages. We use regular expressions with explicit binders for creation and destruction of names and pinpoint an exact property of these expressions - namely memory-finiteness - identifying a subclass of expressions denoting exactly regular nominal languages.

Subject Classification

ACM Subject Classification
  • Theory of computation → Automata over infinite objects
  • Theory of computation → Formal languages and automata theory
Keywords
  • Kleene Theorem
  • Nominal automata
  • Bracket Algebra

Metrics

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

Related Versions

Supplementary Materials

References

  1. Michal Bielecki, Jan Hidders, Jan Paredaens, Jerzy Tyszkiewicz, and Jan Van den Bussche. Navigating with a Browser. In ICALP, pages 764-775, 2002. URL: http://dx.doi.org/10.1007/3-540-45465-9_65.
  2. Mikołaj Bojańczyk. Nominal Monoids. Theory of Computing Systems, 53(2):194-222, 2013. URL: http://dx.doi.org/10.1007/s00224-013-9464-1.
  3. Mikołaj Bojańczyk. Slightly Infinite Sets. A draft of a book, 2017. URL: https://www.mimuw.edu.pl/~bojan/paper/atom-book.
  4. Mikołaj Bojańczyk, Bartek Klin, and Sławomir Lasota. Automata theory in nominal sets. Logical Methods in Computer Science, 10(3):1-44, 2014. URL: http://dx.doi.org/10.2168/LMCS-10(3:4)2014.
  5. 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, 2014. URL: http://dx.doi.org/10.2168/LMCS-10(4:19)2014.
  6. Paul Brunet and Damien Pous. A Formal Exploration of Nominal Kleene Algebra. In MFCS, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.MFCS.2016.22.
  7. Jamie Gabbay, Dan R. Ghica, and Daniela Petrişan. Leaving the Nest: Nominal Techniques for Variables with Interleaving Scopes. In CSL, volume 41, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.CSL.2015.374.
  8. Michael Kaminski and Nissim Francez. Finite-memory automata. Theoretical Computer Science, 134(2):329-363, 1994. URL: http://dx.doi.org/10.1016/0304-3975(94)90242-9.
  9. Michael Kaminski and Tony Tan. Regular Expressions for Languages over Infinite Alphabets. In Computing and Combinatorics, 2004. URL: http://dx.doi.org/10.1007/978-3-540-27798-9_20.
  10. Dexter Kozen, Konstantinos Mamouras, and Alexandra Silva. Completeness and Incompleteness in Nominal Kleene Algebra. In RAMiCS, 2015. URL: http://dx.doi.org/10.1007/978-3-319-24704-5_4.
  11. Dexter Kozen, Konstantinos Mamouras, Alexandra Silva, and Daniela Petrişan. Nominal Kleene Coalgebra. In ICALP, volume 9135, pages 290-302, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47666-6.
  12. Alexander Kurz, Tomoyuki Suzuki, and Emilio Tuosto. A Characterisation of Languages on Infinite Alphabets with Nominal Regular Expressions. In TCS, pages 193-208, 2012. Google Scholar
  13. Alexander Kurz, Tomoyuki Suzuki, and Emilio Tuosto. On Nominal Regular Languages with Binders. In FoSSaCS, pages 255-269, 2012. Google Scholar
  14. Leonid Libkin, Tony Tan, and Domagoj Vrgoč. Regular Expressions for Data Scientists. Journal of Computer and System Sciences, 81(7):1278-1287, 2015. URL: http://dx.doi.org/10.1016/j.jcss.2015.03.005.
  15. Andrzej S Murawski, Steven J Ramsay, and Nikos Tzevelekos. Polynomial-Time Equivalence Testing for Deterministic Fresh-Register Automata. In MFCS, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.MFCS.2018.72.
  16. Frank Neven, Thomas Schwentick, and Victor Vianu. Finite state machines for strings over infinite alphabets. ACM Transactions on Computational Logic, 5(3):403-435, 2004. URL: http://dx.doi.org/10.1145/1013560.1013562.
  17. Andrew M. Pitts. Nominal Sets: Names and Symmetry in Computer Science. Cambridge University Press, New York, NY, USA, 2013. Google Scholar
  18. Lutz Schröder, Dexter Kozen, Stefan Milius, and Thorsten Wißmann. Nominal Automata with Name Binding. In FoSSaCS, pages 124-142, 2017. URL: http://dx.doi.org/10.1007/978-3-662-54458-7_8.
  19. Thomas Schwentick. Automata for XML - A survey. Journal of Computer and System Sciences, 73(3):289-315, 2007. URL: http://dx.doi.org//10.1016/j.jcss.2006.10.003.
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 Imprint Privacy Contact