Talk "Positive Data Languages"

by Stefan Milius

Wed, 07 February 2024 at 10:00 am in Salzburg, Austria

Joint work with: Florian Frank and Henning Urbat

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 Bojanczyk, Klin, and Lasota. As our main contribution we provide a number of quivalent 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.