Abstract-I ett dataord varje position bär en etikett från ett finit alfabet och ett datavärde från någon oändlig domän. Dessa modeller har redan övervägts i sfären av halvstrukturerade data, tidsinställda automater och förlängd tidslogik. Det visas att tillfredsställelsen för den tvåvariabla första ordningen logik FO 2 (, <,+1) är deciderbar över ändliga och över oändliga data ord, där  till är en binär predikat testa datavärdet jämlikhet och +1, < är den vanliga efterträdaren och ordningen predikat. Problemets komplexitet är minst lika svår att nå som Petri netto. Flera utvidgningar av logiken beaktas, en del är fortfarande avgörande medan en del är obeslutsamma.
Huvudresultatet av REF är att tillfredsställandet av FO 2 (-, <, +1) är decidable, genom en dubbelt exponentiell tidsreduktion till nonempty av multicounter automata.
Two-Variable Logic on Words with Data
{'venue': "21st Annual IEEE Symposium on Logic in Computer Science (LICS'06)", 'journal': "21st Annual IEEE Symposium on Logic in Computer Science (LICS'06)", 'mag_field_of_study': ['Mathematics', 'Computer Science']}