XPath evaluation in linear time

Speaker(s)

Paweł Parys

Affiliation

Uniwersytet Warszawski

Date

April 16, 2008, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

We consider a fragment of XPath where attribute values can only 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.

---