DROPS

Document

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

DOI: 10.4230/LIPIcs.ICALP.2026.181

Set Automata and Limits of Decidability of Two-Variable Logic on Data Words

Authors: Shibashis Guha, Amaldev Manuel, and S P Rishal

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

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.

Cite as

Shibashis Guha, Amaldev Manuel, and S P Rishal. Set Automata and Limits of Decidability of Two-Variable Logic on Data Words. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 181:1-181:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{guha_et_al:LIPIcs.ICALP.2026.181,
  author =	{Guha, Shibashis and Manuel, Amaldev and Rishal, S P},
  title =	{{Set Automata and Limits of Decidability of Two-Variable Logic on Data Words}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{181:1--181:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael 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.2026.181},
  URN =		{urn:nbn:de:0030-drops-265696},
  doi =		{10.4230/LIPIcs.ICALP.2026.181},
  annote =	{Keywords: Data words, Two-variable FO, Class automata, Finite semigroups, Decidability}
}

Search Results

Documents authored by Rishal, S P

Set Automata and Limits of Decidability of Two-Variable Logic on Data Words

Abstract

Cite as

Thanks for your feedback!

Could not send message