Efficient static analysis of XML paths and types

We present an algorithm to solve XPath decision problems under regular tree type constraints and show its use to statically type-check XPath queries. To this end, we prove the decidability of a logic with converse for finite ordered trees whose time complexity is a simple exponential of the size of a formula. The logic corresponds to the alternation free modal mu-calculus without greatest fixpoint, restricted to finite trees, and where formulas are cycle-free.


Published in:
Acm Sigplan Notices, 42, 342-351
Year:
2007
Keywords:
Laboratories:




 Record created 2012-07-04, last modified 2018-12-03


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)