Satisfiability of downward XPath

Speaker(s)

Diego Figueira

Affiliation

Laboratoire Spécification et Vérification

Date

Oct. 13, 2010, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

XPath is a logic for finite data trees, and the downward fragment restricts the syntax by allowing only descending paths. I will show that downward XPath has a decidable satisfiability problem. For this, I will work with an automaton model that captures the logic and has a decidable (Exptime) emptiness problem. 

---