Querying Unranked Trees with Stepwise Tree Automata

Abstract : The problem of selecting nodes in unranked trees is the most basic querying problem for XML. We propose stepwise tree automata for querying unranked trees. Stepwise tree automata can express the same monadic queries as monadic Datalog and monadic second-order logic. We prove this result by reduction to the ranked case, via a new systematic correspondence that relates unranked and ranked queries.
Document type :
Conference papers
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/inria-00536529
Contributor : Joachim Niehren <>
Submitted on : Tuesday, November 16, 2010 - 1:41:40 PM
Last modification on : Thursday, February 21, 2019 - 10:52:49 AM
Long-term archiving on : Thursday, February 17, 2011 - 2:58:34 AM

File

stepwise.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00536529, version 1

Collections

Citation

Julien Carme, Joachim Niehren, Marc Tommasi. Querying Unranked Trees with Stepwise Tree Automata. 19th International Conference on Rewriting Techniques and Applications, 2004, Aachen, Georgia. pp.105--118. ⟨inria-00536529⟩

Share

Metrics

Record views

443

Files downloads

365