Varieties of data languages
Urbat H, Milius S (2019)
Publication Type: Conference contribution
Publication year: 2019
Journal
Publisher: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Book Volume: 132
Conference Proceedings Title: Leibniz International Proceedings in Informatics, LIPIcs
Event location: Patras
ISBN: 9783959771092
DOI: 10.4230/LIPIcs.ICALP.2019.130
Abstract
We establish an Eilenberg-type correspondence for data languages, i.e. languages over an infinite alphabet. More precisely, we prove that there is a bijective correspondence between varieties of languages recognized by orbit-finite nominal monoids and pseudovarieties of such monoids. This is the first result of this kind for data languages. Our approach makes use of nominal Stone duality and a recent category theoretic generalization of Birkhoff-type theorems that we instantiate here for the category of nominal sets. In addition, we prove an axiomatic characterization of weak pseudovarieties as those classes of orbit-finite monoids that can be specified by sequences of nominal equations, which provides a nominal version of a classical theorem of Eilenberg and Schützenberger.
Authors with CRIS profile
Henning Urbat
Lehrstuhl für Informatik 8 (Theoretische Informatik)
Stefan Milius
Lehrstuhl für Informatik 8 (Theoretische Informatik)
How to cite
APA:
Urbat, H., & Milius, S. (2019). Varieties of data languages. In Ioannis Chatzigiannakis, Christel Baier, Stefano Leonardi, Paola Flocchini (Eds.), Leibniz International Proceedings in Informatics, LIPIcs. Patras, GR: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing.
MLA:
Urbat, Henning, and Stefan Milius. "Varieties of data languages." Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, Patras Ed. Ioannis Chatzigiannakis, Christel Baier, Stefano Leonardi, Paola Flocchini, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2019.
BibTeX: Download