DROPS

Document

Track B: Automata, Logic, Semantics, and Theory of Programming

DOI: 10.4230/LIPIcs.ICALP.2023.114

Nominal Topology for Data Languages

Authors: Fabian Birkmann, Stefan Milius, and Henning Urbat

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

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

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)

Copy BibTex To Clipboard

@InProceedings{birkmann_et_al:LIPIcs.ICALP.2023.114,
  author =	{Birkmann, Fabian and Milius, Stefan and Urbat, Henning},
  title =	{{Nominal Topology for Data Languages}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{114:1--114:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.114},
  URN =		{urn:nbn:de:0030-drops-181662},
  doi =		{10.4230/LIPIcs.ICALP.2023.114},
  annote =	{Keywords: Nominal sets, Stone duality, Profinite space, Data languages}
}

Search Results

Documents authored by Birkmann, Fabian

Nominal Topology for Data Languages

Abstract

Cite as

Thanks for your feedback!

Could not send message