research article
Efficient static analysis of XML paths and types
Geneves, Pierre
•
Layaida, Nabil
•
Schmitt, Alan
2007
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.
Type
research article
Web of Science ID
WOS:000253409000034
Author(s)
Geneves, Pierre
Layaida, Nabil
Schmitt, Alan
Date Issued
2007
Published in
Volume
42
Start page
342
End page
351
Subjects
Editorial or Peer reviewed
REVIEWED
Written at
EPFL
EPFL units
Available on Infoscience
July 4, 2012
Use this identifier to reference this record