You are not logged in |
XPath evaluation in linear time
- Speaker(s)
- Paweł Parys
- Affiliation
- Uniwersytet Warszawski
- Date
- April 29, 2009, 2:15 p.m.
- Room
- room 5870
- Seminar
- Seminar Automata Theory
We consider a fragment of XPath where attribute values can be tested for equality (FOXPath). We show that for any fixed unary query in this fragment, the set of nodes that satisfy the query can be calculated in time linear in the document size and polynomial in the query size. When we allow arbitrary regular expressions in path expressions, the complexity in the query size is exponential.
