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

Shibashis Guha, Amaldev Manuel, S P Rishal

We extend the two-variable logic on data words with guarded regular binary predicates of the form $\tilde{L}(x,y)$ that is true if positions $x$ and $y$ are in the same class a…