Two-Variable Logic with Two Order Relations

Details Two-Variable Logic with Two Order Relations Two-Variable Logic with Two Order Relations

2011-10-07

arxiv.org/abs/1110.1439v3

LMCS 8 (1:15) 2012

Computer Science

Logic in Computer Science

Scientific paper

10.2168/LMCS-8(1:15)2012

It is shown that the finite satisfiability problem for two-variable logic over structures with one total preorder relation, its induced successor relation, one linear order relation and some further unary relations is EXPSPACE-complete. Actually, EXPSPACE-completeness already holds for structures that do not include the induced successor relation. As a special case, the EXPSPACE upper bound applies to two-variable logic over structures with two linear orders. A further consequence is that satisfiability of two-variable logic over data words with a linear order on positions and a linear order and successor relation on the data is decidable in EXPSPACE. As a complementing result, it is shown that over structures with two total preorder relations as well as over structures with one total preorder and two linear order relations, the finite satisfiability problem for two-variable logic is undecidable.

Affiliated with

Also associated with

No associations

Rating

Two-Variable Logic with Two Order Relations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Two-Variable Logic with Two Order Relations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Two-Variable Logic with Two Order Relations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-132499