Paper Info
Title
Xml Navigation And Transformation By Tree-Walking Automata And Transducers With Visible And Invisible Pebbles
Abstract
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. (C) 2020 Elsevier B.V. All rights reserved.
Year
DOI
Venue
2018
10.1016/j.tcs.2020.10.030
THEORETICAL COMPUTER SCIENCE
Keywords
Field
DocType
Tree transducers, Tree-walking automata, Pebbles, XML document navigation, XML document transformation
Discrete mathematics,Conjunctive query,Binary pattern,Path expression,Automaton,Decidability,Tree automaton,Time complexity,Recursion,Mathematics
Journal
Volume
ISSN
Citations 
850
0304-3975
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Joost Engelfriet12783212.93
Hendrik Jan Hoogeboom258058.38
Bart Samwel3896.72