1. Mikołaj Bojańczyk, Pawel Parys
   XPath evaluation in linear time. J. ACM, 2011   PDF

2. Mikołaj Bojańczyk, Pawel Parys
   Efficient Evaluation of Nondeterministic Automata Using Factorization Forests. ICALP (1), 2010   PDF

3. Mikołaj Bojańczyk, Diego Figueira
   Efficient evaluation for a temporal logic on changing XML documents. PODS  PDF

This is a group of algorithms that work with XML documents in linear or almost linear time. This is in contrast with the XML motivated algorithms on data words and data trees, where typically the running time is exponential or much worse. The first paper shows that XPath can be evaluated in linear time (improving on previous quadratic algorithms), while the second paper tries to explain this phenomenon using automata theory. The last paper considers evolving XML documents. It describes a logic that can express properties like “if a node in the document gets label at some point in time, then at later points in time all of its descendants will have label “. The main contribution is an algorithm that runs in time where is the number of edits, and is a constant that depends (unfortunately, in a nonelementary way) on the formula.

Paper [1] is a journal version of

• Mikołaj Bojańczyk, Pawel Parys
  XPath evaluation in linear time. PODS, 2008   PDF

and a PODS 2009 paper by Paweł Parys.