Mikołaj Bojańczyk

July 14, 2015

Mikołaj Bojańczyk, Pawel Parys

*XPath evaluation in linear time.*J. ACM, 2011 PDFMikołaj Bojańczyk, Pawel Parys

*Efficient Evaluation of Nondeterministic Automata Using Factorization Forests.*ICALP (1), 2010 PDFMikoł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.

## Leave a Reply