Streaming Tree Transducers
From MaRDI portal
Publication:3166998
DOI10.1007/978-3-642-31585-5_8zbMATH Open1367.68157arXiv1104.2599OpenAlexW2764317813MaRDI QIDQ3166998FDOQ3166998
Authors: Loris D'Antoni, Rajeev Alur 
Publication date: 1 November 2012
Published in: Journal of the ACM, Automata, Languages, and Programming (Search for Journal in Brave)
Abstract: 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 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 in linear time 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). Existing models of tree transducers either cannot implement all MSO-definable transformations, or require regular look ahead that prohibits single-pass implementation. We show a variety of analysis problems such as type-checking and checking functional equivalence are solvable for our model.
Full work available at URL: https://arxiv.org/abs/1104.2599
Recommendations
- Streaming Tree Transducers
- Streaming tree automata
- Streaming ranked-tree-to-string transducers
- Streaming ranked-tree-to-string transducers
- Foundations of Software Science and Computation Structures
- Programming Languages and Systems
- Translation of tree-processing programs into stream-processing programs based on ordered linear type
- Modular tree transducers
- scientific article; zbMATH DE number 4041320
- Expressiveness of streaming string transducers
Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)
Cited In (23)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Look-ahead removal for total deterministic top-down tree transducers
- Copyful Streaming String Transducers
- Copyless cost-register automata: structure, expressiveness, and closure properties
- Regular Programming for Quantitative Properties of Data Streams
- Streaming transducers for algorithmic verification of single-pass list-processing programs
- Multiple context-free tree grammars: lexicalization and characterization
- Streaming ranked-tree-to-string transducers
- Streaming tree automata
- Title not available (Why is that?)
- Determinacy and rewriting of functional top-down and MSO tree transformations
- Optimizing term rewriting with creeper trace transducers
- Regular transducer expressions for regular transformations
- Title not available (Why is that?)
- Streamable regular transductions
- A Pushdown Machine for Recursive XML Processing
- Translation of tree-processing programs into stream-processing programs based on ordered linear type
- Expressiveness of streaming string transducers
- Title not available (Why is that?)
- Streaming Tree Transducers
- Regular Transformations of Data Words Through Origin Information
- Streamability of nested word transductions
This page was built for publication: Streaming Tree Transducers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3166998)
