Extending Büchi Automata with Constraints on Data Values

Details Extending Büchi Automata with Constraints on Data Values Extending Büchi Automata with Constraints on Data Values

2010-12-24

arxiv.org/abs/1012.5439v1

Computer Science

Logic in Computer Science

Scientific paper

Recently data trees and data words have received considerable amount of attention in connection with XML reasoning and system verification. These are trees or words that, in addition to labels from a finite alphabet, carry data values from an infinite alphabet (data). In general it is rather hard to obtain logics for data words and trees that are sufficiently expressive, but still have reasonable complexity for the satisfiability problem. In this paper we extend and study the notion of B\"uchi automata for omega-words with data. We prove that the emptiness problem for such extension is decidable in elementary complexity. We then apply our result to show the decidability of two kinds of logics for omega-words with data: the two-variable fragment of first-order logic and some extensions of classical linear temporal logic for omega-words with data.

Affiliated with

Also associated with

No associations

Rating

Extending Büchi Automata with Constraints on Data Values 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 Extending Büchi Automata with Constraints on Data Values, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Extending Büchi Automata with Constraints on Data Values will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-93800