A Direct Translation from XPath to Nondeterministic Automata

Alberto Mendelzon International Workshop on Foundations of Data Management 2011.

社会科学（总论）;计算机科学

Nadime Francis ; Claire David ; Leonid Libkin

Others  :  http://ceur-ws.org/Vol-749/paper7.pdf
PID  :  41581

来源: CEUR

【 摘 要 】

Since navigational aspects of XPath correspond to first-order definability, it has been proposed to use the analogy with the very successful technique of translating LTL into automata, and produce efficient translations of XPath queries into automata on unranked trees. These translations can then be used for a variety of reasoning tasks such as XPath consistency, or optimization, under XML schema constraints. In the verification scenarios, translations into both nondeterministic and alternating automata are used. But while a direct translation from XPath into alternating automata is known, only an indirect translation into nondeterministic automata - going via intermediate logics - exists. A direct translation is desirable as most XML specifications have particularly nice translations into nondeterministic automata and it is natural to use such automata to reason about XPath and schemas. The goal of the paper is to produce such a direct translation of XPath into nondeterministic automata.