@TECHREPORT{TR-jeff-karl:sep-2005, AUTHOR = "Jeffrey Palm and Karl J. Lieberherr", TITLE = "Improving XPath Evaluation with Strategies", INSTITUTION = "Northeastern University", YEAR = 2005, MONTH = "September", NUMBER = "NU-CCIS-05-30 }

Paper .

Notes by Karl:

Can theorem 1 be strengthened from exponential (2**n) to faster growing functions? For example, can we construct an infinite sequence of query/DTD/document triples so that the naive evaluation will visit A(c,n) nodes, where A is the Ackermann function and c a constant > 3?