2026-09-08T01:21:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26569 2026-09-05T19:48:10Z ddc:004 open_access

Set Automata and Limits of Decidability of Two-Variable Logic on Data Words Guha, Shibashis Manuel, Amaldev Rishal, S P Data words Two-variable FO Class automata Finite semigroups Decidability We extend the two-variable logic on data words [Bojańczyk et al., 2011] with guarded regular binary predicates of the form L̃(x,y) that is true if positions x and y have the same data value and the factor strictly between x and y is in the regular language L. We characterise the class of aperiodic monoids for which the extension of the two-variable logic with guarded predicates recognised by the monoid is decidable, namely the class of idempotent monoids whose two-sided ideals are linearly ordered, called linear bands. For this, we introduce an automata formalism, set automata, that is equivalent to the class automata of Bojańczyk and Lasota and thus has an undecidable emptiness problem. The set updates used in the automaton form a semigroup of relations. We identify a subclass of set automata called ordered quasi-normal set automata that has a decidable emptiness problem by reduction to the emptiness problem of ordered multicounter automata. We show that the two-variable logic extended with guarded regular predicates recognised by a monoid M is expressively equivalent to a quasi-normal set automaton with the monoid of relations M. In particular, if M is a linear band then the resulting automaton is ordered, and the decidability result follows. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shibashis Guha and Amaldev Manuel and S P Rishal 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.181 urn:nbn:de:0030-drops-265696 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.181 eng https://creativecommons.org/licenses/by/4.0/legalcode