Positive Data Languages

Frank F, Milius S, Urbat H (2023)

Publication Language: English

Publication Type: Journal article, Online publication

Publication year: 2023

Journal

LIPIcs : Leibniz International Proceedings in Informatics Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik

Book Volume: 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Pages Range: 48:1-48:15

Article Number: 48

Journal Issue: 272

URI: https://drops.dagstuhl.de/opus/volltexte/2023/18582

DOI: 10.4230/LIPIcs.MFCS.2023.48

Open Access Link: https://drops.dagstuhl.de/opus/volltexte/2023/18582

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.

Authors with CRIS profile

Florian Frank Graduiertenkolleg 2475 Cyberkriminalität und Forensische Informatik Stefan Milius Lehrstuhl für Informatik 8 (Theoretische Informatik) Henning Urbat Lehrstuhl für Informatik 8 (Theoretische Informatik)

Related research project(s)

Cyberkriminalität und forensische Informatik (Cybercrime) Oct. 1, 2019 - March 31, 2024

How to cite

APA:

Frank, F., Milius, S., & Urbat, H. (2023). Positive Data Languages. LIPIcs : Leibniz International Proceedings in Informatics, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)(272), 48:1-48:15. https://doi.org/10.4230/LIPIcs.MFCS.2023.48

MLA:

Frank, Florian, Stefan Milius, and Henning Urbat. "Positive Data Languages." LIPIcs : Leibniz International Proceedings in Informatics 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023).272 (2023): 48:1-48:15.

BibTeX: Download