On reasoning about structural equality in XML: a description logic approach

We define a boolean complete dialect of description logic called DLFDreg that can be used to reason about structural equality in semistructured ordered data in the presence of document type definitions. This application depends on the novel ability of DLFDreg to express functional dependencies over possibly infinite sets of feature paths defined by regular languages. We also present a decision procedure for the associated logical implication problem. The procedure underlies a mapping of such problems to satisfiability problems of DatalognS¬.