hide
Free keywords:
-
Abstract:
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.
