Document Open Access Logo

Nominal Topology for Data Languages

Authors Fabian Birkmann , Stefan Milius , Henning Urbat

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2023.114.pdf
  • Filesize: 0.78 MB
  • 21 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
Keywords
  • Nominal sets
  • Stone duality
  • Profinite space
  • Data languages

Metrics

Abstract

We propose a novel topological perspective on data languages recognizable by orbit-finite nominal monoids. For this purpose, we introduce pro-orbit-finite nominal topological spaces. Assuming globally bounded support sizes, they coincide with nominal Stone spaces and are shown to be dually equivalent to a subcategory of nominal boolean algebras. Recognizable data languages are characterized as topologically clopen sets of pro-orbit-finite words. In addition, we explore the expressive power of pro-orbit-finite equations by establishing a nominal version of Reiterman’s pseudovariety theorem.

Cite As Get BibTex

Fabian Birkmann, Stefan Milius, and Henning Urbat. Nominal Topology for Data Languages. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 114:1-114:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ICALP.2023.114

Author Details

Fabian Birkmann
  • Friedrich-Alexander-Universität Erlangen-Nürnberg, Germany
Stefan Milius
  • Friedrich-Alexander-Universität Erlangen-Nürnberg, Germany
Henning Urbat
  • Friedrich-Alexander-Universität Erlangen-Nürnberg, Germany

Funding

Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – project number 470467389.

References

  1. Jiří Adámek, Liang-Ting Chen, Stefan Milius, and Henning Urbat. Reiterman’s theorem on finite algebras for a monad. ACM Trans. Comput. Log., 22(4):23:1-23:48, 2021. Google Scholar
  2. Jiří Adámek and Jiří Rosický. Locally Presentable and Accessible Categories. London Mathematical Society Lecture Note Series. Cambridge University Press, 1994. Google Scholar
  3. Jorge Almeida. Profinite semigroups and applications. In Structural Theory of Automata, Semigroups, and Universal Algebra, pages 1-45. Springer Netherlands, 2005. Google Scholar
  4. Jorge Almeida and Alfredo Costa. Profinite topologies. In Jean-Éric Pin, editor, Handbook of Automata Theory, pages 615-652. European Mathematical Society Publishing House, Zürich, Switzerland, 2021. Google Scholar
  5. Michał Bielecki, Jan Hidders, Jan Paredaens, Jerzy Tyszkiewicz, and Jan Van den Bussche. Navigating with a browser. In ICALP 2002, volume 2380 of LNCS, pages 764-775. Springer, 2002. Google Scholar
  6. Garrett Birkhoff. On the Structure of Abstract Algebras. Mathematical Proceedings of the Cambridge Philosophical Society, 31(4):433-454, 1935. Google Scholar
  7. Mikołaj Bojańczyk. Nominal monoids. Theory Comput. Syst., 53(2):194-222, 2013. URL: https://doi.org/10.1007/s00224-013-9464-1.
  8. Mikołaj Bojańczyk. Recognisable languages over monads. In DLT 2015, volume 9168 of LNCS, pages 1-13. Springer, 2015. Google Scholar
  9. Mikołaj Bojańczyk, Bartek Klin, and Sławomir Lasota. Automata theory in nominal sets. Log. Methods Comput. Sci., 10(3), 2014. URL: https://doi.org/10.2168/LMCS-10(3:4)2014.
  10. Mikołaj Bojańczyk and Rafał Stefański. Single-use automata and transducers for infinite alphabets. In ICALP 2020, volume 168 of LIPIcs, pages 113:1-113:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.113.
  11. Benedikt Bollig, Peter Habermehl, Martin Leucker, and Benjamin Monmege. A robust class of data languages and an application to learning. Log. Meth. Comput. Sci., 10(4:19):23pp., 2014. URL: https://doi.org/10.2168/LMCS-10(4:19)2014.
  12. Liang-Ting Chen, Jiří Adámek, Stefan Milius, and Henning Urbat. Profinite monads, profinite equations, and Reiterman’s theorem. In FOSSACS 2019, volume 9634 of LNCS, pages 531-547. Springer, 2016. URL: https://doi.org/10.1007/978-3-662-49630-5_31.
  13. Thomas Colcombet, Clemens Ley, and Gabriele Puppis. Logics with rigidly guarded data tests. Log. Methods Comput. Sci., 11(3), 2015. Google Scholar
  14. Samuel Eilenberg. Automata, Languages, and Machines. Elsevier Science, 1974. Google Scholar
  15. Samuel Eilenberg and Marcel-Paul Schützenberger. On pseudovarieties. Advances Math., 10:413-418, 1976. Google Scholar
  16. Murdoch James Gabbay. Nominal algebra and the HSP theorem. J. Log. Comput., 19(2):341-367, 2009. URL: https://doi.org/10.1093/logcom/exn055.
  17. Murdoch James Gabbay, Tadeusz Litak, and Daniela Petrisan. Stone Duality for Nominal Boolean Algebras with N. In CALCO 2011, volume 6859 of LNCS, pages 192-207. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-22944-2_14.
  18. Mai Gehrke, Serge Grigorieff, and Jean-Eric Pin. Duality and equational theory of regular languages. In ICALP 2008, volume 5126 of LNCS, pages 246-257. Springer, 2008. Google Scholar
  19. Mai Gehrke, Serge Grigorieff, and Jean-Eric Pin. A topological approach to recognition. In ICALP 2010, volume 6199 of LNCS, pages 151-162. Springer, 2010. Google Scholar
  20. Mai Gehrke, Daniela Petrişan, and Luca Reggio. The Schützenberger product for syntactic spaces. In ICALP 2016, volume 55 of LIPIcs, pages 112:1-112:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. Google Scholar
  21. Mai Gehrke, Daniela Petrişan, and Luca Reggio. Quantifiers on languages and codensity monads. In LICS 2017, pages 1-12. IEEE Computer Society, 2017. Google Scholar
  22. Radu Grigore, Dino Distefano, Rasmus Petersen, and Nikos Tzevelekos. Runtime verification based on register automata. In TACAS 2013, volume 7795 of LNCS, pages 260-276. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-36742-7_19.
  23. Matthew Hennessy. A fully abstract denotational semantics for the pi-calculus. Theoret. Comput. Sci., 278:53-89, 2002. URL: https://doi.org/10.1016/S0304-3975(00)00331-5.
  24. Michael Kaminski and Nissim Francez. Finite-memory automata. Theor. Comput. Sci., 134(2):329-363, 1994. URL: https://doi.org/10.1016/0304-3975(94)90242-9.
  25. Kenneth Krohn and John Rhodes. Algebraic theory of machines. I. Prime decomposition theorem for finite semigroups and machines. Trans. Am. Math. Soc., 116:450-464, 1965. Google Scholar
  26. Klaas Kürtz, Ralf Küsters, and Thomas Wilke. Selecting theories and nonce generation for recursive protocols. In FSME 2007, pages 61-70. ACM, 2007. Google Scholar
  27. Alexander Kurz and Daniela Petrisan. On universal algebra over nominal sets. Math. Struct. Comput. Sci., 20(2):285-318, 2010. URL: https://doi.org/10.1017/S0960129509990399.
  28. Saunders MacLane. Categories for the Working Mathematician. Springer-Verlag, 1971. Google Scholar
  29. R. McNaughton and S. Papert. Counter-free Automata. M.I.T. Press research monographs. M.I.T. Press, 1971. Google Scholar
  30. Stefan Milius and Henning Urbat. Equational axiomatization of algebras with structure. In FOSSACS 2019, volume 11425 of LNCS, pages 400-417. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-17127-8_23.
  31. Frank Neven, Thomas Schwentick, and Victor Vianu. Finite state machines for strings over infinite alphabets. ACM Trans. Comput. Log., 5(3):403-435, 2004. URL: https://doi.org/10.1145/1013560.1013562.
  32. Daniela Petrişan. Investigations into Algebra and Topology over Nominal Sets. PhD thesis, University of Leicester, 2012. Google Scholar
  33. Jean-Eric Pin. Profinite methods in automata theory. In STACS 2009, volume 3 of LIPIcs, pages 31-50. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany, 2009. URL: https://doi.org/10.4230/LIPIcs.STACS.2009.1856.
  34. Jean-Eric Pin and Pascal Weil. A Reiterman theorem for pseudovarieties of finite first-order structures. Algebra Universalis, 35(4):577-595, 1996. Google Scholar
  35. Nicholas Pippenger. Regular languages and Stone duality. Theory Comput. Syst., 30(2):121-134, 1997. URL: https://doi.org/10.1007/s002240000045.
  36. Andrew M. Pitts. Nominal Sets: Names and Symmetry in Computer Science. Cambridge University Press, 2013. Google Scholar
  37. Jan Reiterman. The Birkhoff theorem for finite algebras. Algebra Universalis, 14(1):1-10, 1982. Google Scholar
  38. Julian Salamanca. Unveiling eilenberg-type correspondences: Birkhoff’s theorem for (finite) algebras + duality. CoRR, 2017. URL: https://arxiv.org/abs/1702.02822.
  39. Lutz Schröder, Dexter Kozen, Stefan Milius, and Thorsten Wißmann. Nominal automata with name binding. In FOSSACS 2017, pages 124-142, 2017. Google Scholar
  40. Marcel Paul Schützenberger. On finite monoids having only trivial subgroups. Information and Control, 8(2):190-194, 1965. Google Scholar
  41. Imre Simon. Piecewise testable events. In H. Brakhage, editor, Automata Theory and Formal Languages, pages 214-222. Springer, 1975. Google Scholar
  42. Henning Urbat, Jiří Adámek, Liang-Ting Chen, and Stefan Milius. Eilenberg theorems for free. In MFCS 2017, volume 83 of LIPIcs, pages 43:1-43:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.MFCS.2017.43.
  43. Henning Urbat, Daniel Hausmann, Stefan Milius, and Lutz Schröder. Nominal Büchi automata with name allocation. In CONCUR 2021, pages 4:1-4:16, 2021. URL: https://doi.org/10.4230/LIPIcs.CONCUR.2021.4.
  44. Henning Urbat and Stefan Milius. Varieties of data languages. In ICALP 2019, volume 132 of LIPIcs, pages 130:1-130:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.130.
  45. Thomas Wilke. An Eilenberg theorem for infinity-languages. In ICALP 1991, volume 510 of LNCS, pages 588-599. Springer, 1991. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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