The Complexity of Reasoning about Pattern-based XML Schemas

摘要

In a recent paper, Martens et al. introduced a specification mechanism for {XML} tree languages, based on rules of the form r ! s, where r, s are regular expressions. Sets of such rules can be interpreted in an existential or a universal fashion. An {XML} tree is existentially valid with respect to a rule set, if for each node there is a rule such that the root path of the node matches r and the children sequence of the node matches s. It is universally valid if each node matching r also matches s. This paper investigates the complexity of reasoning about such rule sets, in particular the satisfiability and the implication problem. Whereas, in general these reasoning problems are complete for ExpTime, two important fragments are identified with PSpace and PTime complexity, respectively.