Paper Info
Title
XML transformation by tree-walking transducers with 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 n-ary 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 pebbletree 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 ofthe typechecking problem for conjunctive queries that use MSO definable binary patterns can often be reduced through the use of invisible pebbles.
Year
DOI
Venue
2007
10.1145/1265530.1265540
PODS
Keywords
Field
DocType
mso definable n-ary pattern,pebble tree automaton,xpath-like formalism,invisible pebble,regular tree language,mso definable binary pattern,xml transformation,decidable typechecking problem,arbitrary mso definable test,tree-walking transducers,pebble tree,pebble tree transducer,time complexity,conjunctive queries,path expressions,xml
Discrete mathematics,Conjunctive query,Binary pattern,Computer science,Automaton,Path expression,Decidability,Theoretical computer science,Tree automaton,Time complexity,Recursion
Conference
Citations 
PageRank 
References 
15
0.61
25
Authors
3
Name
Order
Citations
PageRank
Joost Engelfriet12783212.93
Hendrik Jan Hoogeboom258058.38
Bart Samwel3896.72