Nominal Topology for Data Languages
Birkmann F, Milius S, Urbat H (2023)
Publication Type: Conference contribution
Publication year: 2023
Journal
Publisher: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Book Volume: 261
Conference Proceedings Title: Leibniz International Proceedings in Informatics, LIPIcs
Event location: Paderborn
ISBN: 9783959772785
DOI: 10.4230/LIPIcs.ICALP.2023.114
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.
Authors with CRIS profile
Fabian Birkmann
Lehrstuhl für Informatik 8 (Theoretische Informatik)
Stefan Milius
Lehrstuhl für Informatik 8 (Theoretische Informatik)
Henning Urbat
Lehrstuhl für Informatik 8 (Theoretische Informatik)
How to cite
APA:
Birkmann, F., Milius, S., & Urbat, H. (2023). Nominal Topology for Data Languages. In Kousha Etessami, Uriel Feige, Gabriele Puppis (Eds.), Leibniz International Proceedings in Informatics, LIPIcs. Paderborn, DE: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing.
MLA:
Birkmann, Fabian, Stefan Milius, and Henning Urbat. "Nominal Topology for Data Languages." Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, Paderborn Ed. Kousha Etessami, Uriel Feige, Gabriele Puppis, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023.
BibTeX: Download