You are not logged in | Log in

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.