XML Navigation and Transformation by Tree-Walking Automata and Transducers with Visible and Invisible Pebbles
| Autor: | Hendrik Jan Hoogeboom, Bart Samwel, Joost Engelfriet |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
FOS: Computer and information sciences
Theoretical computer science Recursion TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES General Computer Science Computer science Formal Languages and Automata Theory (cs.FL) Computer Science - Formal Languages and Automata Theory 0102 computer and information sciences 02 engineering and technology 01 natural sciences Path expression Theoretical Computer Science Decidability Automaton TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Conjunctive query Tree transducers Tree automaton Time complexity |
| Zdroj: | Theoretical Computer Science, 850, 40-97 |
| DOI: | 10.48550/arxiv.1809.05730 |
| Popis: | The pebble tree automaton and the pebble tree transducer are enhanced by additionally allowing an unbounded number of "invisible" pebbles (as opposed to the usual "visible" ones). The resulting pebble tree automata recognize the regular tree languages (i.e., can validate all generalized DTD's) and hence can find all matches of MSO definable patterns. Moreover, when viewed as a navigational device, they lead to an XPath-like formalism that has a path expression for every MSO definable binary pattern. The resulting pebble tree transducers can apply arbitrary MSO definable tests to (the observable part of) their configurations, they (still) have a decidable typechecking problem, and they can model the recursion mechanism of XSLT. The time complexity of the typechecking problem for conjunctive queries that use MSO definable patterns can often be reduced through the use of invisible pebbles. Comment: 96 pages, 6 figures, 7 tables |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|