Alternating Automata on Data Trees and XPath Satisfiability

Details Alternating Automata on Data Trees and XPath Satisfiability Alternating Automata on Data Trees and XPath Satisfiability

2008-05-03

arxiv.org/abs/0805.0330v4

Computer Science

Logic in Computer Science

23 pages

Scientific paper

A data tree is an unranked ordered tree whose every node is labelled by a letter from a finite alphabet and an element ("datum") from an infinite set, where the latter can only be compared for equality. The article considers alternating automata on data trees that can move downward and rightward, and have one register for storing data. The main results are that nonemptiness over finite data trees is decidable but not primitive recursive, and that nonemptiness of safety automata is decidable but not elementary. The proofs use nondeterministic tree automata with faulty counters. Allowing upward moves, leftward moves, or two registers, each causes undecidability. As corollaries, decidability is obtained for two data-sensitive fragments of the XPath query language.

Affiliated with

Also associated with

No associations

Rating

Alternating Automata on Data Trees and XPath Satisfiability 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 Alternating Automata on Data Trees and XPath Satisfiability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Alternating Automata on Data Trees and XPath Satisfiability will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-512547