2012 | OriginalPaper | Buchkapitel
Streaming Tree Transducers
verfasst von : Rajeev Alur, Loris D’Antoni
Erschienen in: Automata, Languages, and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Theory of tree transducers provides a foundation for understanding expressiveness and complexity of analysis problems for specification languages for transforming hierarchically structured data such as XML documents. We introduce
streaming tree transducers
as an analyzable, executable, and expressive model for transforming unranked ordered trees (and hedges) in a single pass. Given a linear encoding of the input tree, the transducer makes a single left-to-right pass through the input, and computes the output using a finite-state control, a visibly pushdown stack, and a finite number of variables that store output chunks that can be combined using the operations of string-concatenation and tree-insertion. We prove that the expressiveness of the model coincides with transductions definable using monadic second-order logic (MSO). We establish complexity upper bounds of
ExpTime
for
type-checking
and
NExpTime
for checking
functional equivalence
for our model. We consider variations of the basic model when inputs/outputs are restricted to strings and ranked trees, and in particular, present the model of
bottom-up ranked-tree transducers
, which is the first known MSO-equivalent transducer model that processes trees in a bottom-up manner.