loading...
Two-Variable Logic on Words with Data
Seattle, Washington August 12-August 15
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/LICS.2006.5121st Annual IEEE Symposium on Logic i ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
Mikolaj Bojanczyk, Anca Muscholl, Thomas Schwentick, Luc Segoufin, Claire David, "Two-Variable Logic on Words with Data," Logic in Computer Science, Symposium on, pp. 7-16, 21st Annual IEEE Symposium on Logic in Computer Science (LICS'06), 2006.
 
 
BibTex
x
 
@article{ 10.1109/LICS.2006.51,
author = {Mikolaj Bojanczyk and Anca Muscholl and Thomas Schwentick and Luc Segoufin and Claire David},
title = {Two-Variable Logic on Words with Data},
journal ={Logic in Computer Science, Symposium on},
volume = {0},
year = {2006},
issn = {1043-6871},
pages = {7-16},
doi = {http://doi.ieeecomputersociety.org/10.1109/LICS.2006.51},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Logic in Computer Science, Symposium on
TI - Two-Variable Logic on Words with Data
SN - 1043-6871
SP7
EP16
A1 - Mikolaj Bojanczyk,
A1 - Anca Muscholl,
A1 - Thomas Schwentick,
A1 - Luc Segoufin,
A1 - Claire David,
PY - 2006
KW - null
VL - 0
JA - Logic in Computer Science, Symposium on
ER -
 
Mikolaj Bojanczyk, Warsaw University
Anca Muscholl, LIAFA, Paris VII
Thomas Schwentick, Dortmund University
Luc Segoufin, INRIA, Paris XI
Claire David, LIAFA, Paris VII
In a data word each position carries a label from a finite alphabet and a data value from some infinite domain. These models have been already considered in the realm of semistructured data, timed automata and extended temporal logics.

It is shown that satisfiability for the two-variable first-order logic FO^2(~,\le,+1) is decidable over finite and over infinite data words, where ?? is a binary predicate testing the data value equality and +1,\le are the usual successor and order predicates. The complexity of the problem is at least as hard as Petri net reachability. Several extensions of the logic are considered, some remain decidable while some are undecidable.

Citation:
Mikolaj Bojanczyk, Anca Muscholl, Thomas Schwentick, Luc Segoufin, Claire David, "Two-Variable Logic on Words with Data," lics, pp.7-16, 21st Annual IEEE Symposium on Logic in Computer Science (LICS'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.