On Reasoning about Structural Equality in XML: A Description Logic Approach David Toman and Grant E. Weddell   View Paper (PDF)   Return to Research Papers Abstract We define a boolean complete description logic dialect called DLFD_reg $\mathcal{ DLFD}_{\mathrm{reg}}$ 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 DLFD_reg $\mathcal{ DLFD}_{\mathrm{reg}}$ to express functional dependencies over sets of possibly infinite 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 Datalog $_{nS}^{\vee,\neg}$ and in turn to the Ackermann case of the decision problem. ©2004 Association for Computing Machinery