Streaming tree transducers

We introduce streaming tree transducers as an analyzable, executable, and expressive model for transforming unranked ordered trees. 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 set of variables storing output chunks that can be combined using concatenation and insertion. We prove the model to be equivalent to monadic second-order logic transductions. We show complexity bounds of ExpTime for type-checking and NExpTime for equivalence.

Authors

• Loris D'Antoni
• Rajeev Alur

Keywords

No keywords are indexed for this paper.