Set Automata and Limits of Decidability of Two-Variable Logic on Data Words
Shibashis Guha, Amaldev Manuel, S P Rishal · 2026
Read Set Automata and Limits of Decidability of Two-Variable Logic on Data Words by Shibashis Guha, Amaldev Manuel, S P Rishal (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-09077.txt.
Introduction
Shibashis Guha, Amaldev Manuel, and S P Rishal study a logic for data words, sequences where each position carries a symbol and a data value. They extend the two-variable fragment of this logic with guarded predicates that compare two positions in the same class when the text between them matches a regular pattern.
The authors pin down exactly which algebraic structures, called monoids, keep this extended logic decidable: the idempotent ones whose two-sided ideals form a chain. To prove it they introduce set automata, a machine model tied to an older class-automata idea, and isolate a well-behaved subclass whose emptiness question can be decided. The results draw a sharp line between tractable and intractable versions of the logic.
Catalog record
| CREATOR | Shibashis Guha, Amaldev Manuel, S P Rishal |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 147 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.09077
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Set Automata and Limits of Decidability of Two-Variable Logic on Data Words Shibashis Guha, Amaldev Manuel, S P Rishal Abstract We extend the two-variable logic on data words [ 4 ] with guarded regular binary predicates of the form L ~ ( x , y ) \widetilde{L}(x,y) that is true if positions x x and y y are in the same class and the factor strictly between x x and y y is in the regular language L L . We characterise the class of 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. 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. 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 semigroup S S is expressively equivalent to a quasi-normal set automaton with the semigroup of transformations S S . In particular, if S S is a linear band monoid then the resulting automaton is ordered, and the decidability result follows. Tata Institute of Fundamental [email protected] supported by CEFIPRA project no. 7302-I and by the Department of Atomic Energy, Government of India, under project no. RTI4014Indian Institute of Technology [email protected] Sarva [email protected] \declaretheorem [name=Theorem, sibling=definition]thm ccs Theory of computation Logic and verification keywords Data words, Two-variable FO, Class automata, Finite semigroups, Decidability † † runningauthor: S. Guha, A. Manuel, and S P. Rishal † † copyright: Jane Open Access and Joan R. Public † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction A data word is a finite sequence of pairs (a_{i},d_{i})\in\Sigma\times\mathcal{D} where \Sigma is a finite alphabet and \mathcal{D} is an infinite domain of data values that can be tested only for equality. A set of data words L is called a data language . In most cases (including this work) L is assumed to be closed under permutations of the set \mathcal{D} , that is, every occurrence of some data value d_{i} can be replaced with another data value d_{j}\neq d_{i} as long as such a mapping is a permutation. Thus the specific data values considered are not important to the study and we only capture properties involving equality of data values. For our purposes, L can be represented as a collection of relational first-order structures of the form \left([n],(a)_{a\in\Sigma},<,+1\sim\right),\moo 1 where [n] and < denote the set \{1,\ldots,n\} and the natural order on it, the unary predicates (a)_{a\in\Sigma} denotes the labelling by \Sigma , and \sim is the equivalence relation on positions given by data values, i.e., i\sim j if d_{i}=d_{j} . The relation \moo 1 denotes the class successor relation, i.e., i\moo 1=j , if i\sim j and the positions strictly between i and j are not equivalent to them. The class of i is the equivalence class of i under the relation \sim , i.e., the set of all positions labelled with the data value d_{i} . The primary direction in the study of data words has been identifying suitable notions of automata and logics for them (See [ 17 , 2 ] and the survey [ 19 ] ). The models and logics in the literature can broadly be classified into two families: temporal logics (correspondingly, the register automata family) and first-order logics (data automata family). The prominent member of the first family is the freeze-LTL (i.e., LTL with registers) of [ 9 ] , while the most important logic of the latter is the two-variable first-order logic [ 4 ] . In this work we present a decidable, strict extension of the two-variable logic that incorporates some aspects of temporal logics. First we recall the two-variable logic in some detail. For a vocabulary \tau of unary and binary predicates let \mathrm{FO}^{2}[\tau] denote the first-order formulas using the predicates from \tau and the variables x and y . The logic \mathrm{EMSO}^{2}[\tau] consists of formulas of the form \exists X_{1}\ldots\exists X_{n}\,\varphi with \varphi\in\mathrm{FO}^{2}[\overline{X},\tau] , where \overline{X} stands for the monadic second-order predicates X_{1},\ldots,X_{n} that quantify over sets of positions. Certainly, it is natural to consider the first-order logic ( \mathrm{FO} ) with the vocabulary (\Sigma,<,\sim) on data words. However, as one would expect, the satisfiability problem of the logic \mathrm{FO}[\Sigma,<,\sim] is undecidable [ 4 ] . The undecidability persists even if the number of variables is restricted to three. This prompted the study of the two-variable fragment of the logic. For convenience in working with automata, we consider the extension of the first-oder logics with existential monadic second-order predicates. It is shown in [ 4 ] that the satisfiability problem of \mathrm{EMSO}^{2}[\Sigma,<,+1,\sim,\moo 1] is decidable over data words in non-elementary time. The proof is by translating the formulas into an automaton formalism called data automata and showing the decidability of the emptiness problem of data automata. As far as the study of logics over data words is concerned this result is a milestone and despite nearly two decades of active research, \mathrm{FO}^{2} remains as one of the yardstick logics with which any new formalism is measured. Next we look at some examples. The string projection of a data word w is the word \mathrm{str}(w)=a_{1}\cdots a_{n} . Let 1\leq i_{1}<i_{2}<\cdots<i_{k}\leq n be a class of w . The string projection of this class is the word u=a_{i_{1}}\cdots a_{i_{k}} . We say u is a class of w to mean a class whose string projection is u . Example 1 . Let \Sigma=\{\iota,\delta,z\} . We can think of \iota and \delta as increments and decrements of a counter and z as a zero-test. 1. Let L_{1} be the set of all data words where each class is of the form \iota\delta or z . This language is defined by the formula \varphi_{1} where \displaystyle\varphi_{1} \displaystyle:=\forall x\forall y\,(x<y\wedge x\sim y\rightarrow\iota(x)\wedge\delta(y))\wedge((x\sim y\rightarrow x=y)\rightarrow z(x)) (1) 2. Let L_{2} consists of all data words satisfying the property: there is no position labelled by z between each \iota and \delta of the same class. The language L_{2} is not definable in \mathrm{FO}^{2} as noted in [ 19 ] . In fact it is not recognised by the data automata of [ 4 ] , that is equivalent to the logic \mathrm{EMSO}^{2}[\Sigma,<,x+1,\sim,\moo 1] However, L_{2} is definable in freeze-LTL with only forward-looking modalities (Next and Until), a logic with a decidable satisfiability problem (as a trade-off this logic cannot define L_{1} , see [ 19 ] ). To define L_{2} in \mathrm{FO}^{2} , we extend the two-variable logic with the below predicates. Definition 2 (Regular Predicate) . A regular predicate over the alphabet \Sigma is a binary relation of the form L(x,y) where L\subseteq\Sigma^{*} is a regular language. The word