License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2023.48
URN: urn:nbn:de:0030-drops-185828
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18582/
Go to the corresponding LIPIcs Volume Portal

Frank, Florian ; Milius, Stefan ; Urbat, Henning

Positive Data Languages

pdf-format:
LIPIcs-MFCS-2023-48.pdf (0.8 MB)

Abstract

Positive data languages are languages over an infinite alphabet closed under possibly non-injective renamings of data values. Informally, they model properties of data words expressible by assertions about equality, but not inequality, of data values occurring in the word. We investigate the class of positive data languages recognizable by nondeterministic orbit-finite nominal automata, an abstract form of register automata introduced by Bojańczyk, Klin, and Lasota. As our main contribution we provide a number of equivalent characterizations of that class in terms of positive register automata, monadic second-order logic with positive equality tests, and finitely presentable nondeterministic automata in the categories of nominal renaming sets and of presheaves over finite sets.

BibTeX - Entry

@InProceedings{frank_et_al:LIPIcs.MFCS.2023.48,
  author =	{Frank, Florian and Milius, Stefan and Urbat, Henning},
  title =	{{Positive Data Languages}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{48:1--48:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18582},
  URN =		{urn:nbn:de:0030-drops-185828},
  doi =		{10.4230/LIPIcs.MFCS.2023.48},
  annote =	{Keywords: Data Languages, Register Automata, MSO, Nominal Sets, Presheaves}
}

Keywords: Data Languages, Register Automata, MSO, Nominal Sets, Presheaves
Collection: 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Issue Date: 2023
Date of publication: 21.08.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI