On tree transducers for partial functions

DOI10.1016/0020-0190(78)90060-1zbMath0379.94066OpenAlexW2021885035MaRDI QIDQ1247295

Joost Engelfriet

Publication date: 1978

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(78)90060-1

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Visibly Pushdown Transducers with Look-Ahead, Definability results for top-down tree transducers, Decision problems of tree transducers with origin, Branching synchronization grammars with nested tables, Visibly pushdown transducers, How to decide functionality of compositions of top-down tree transducers, Definability Results for Top-Down Tree Transducers, Functionality of compositions of top-down tree transducers is decidable, Deciding whether an attributed translation can be realized by a top-down transducer, Look-ahead removal for total deterministic top-down tree transducers, A complete rewriting system for a monoid of tree transformation classes, Top-down tree transducers with two-way tree walking look-ahead, The use of tree transducers to compute translations between graph algebras, Synthesis of deterministic top-down tree transducers from automatic tree relations, Variants of top-down tree transducers with look-ahead, Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity, Look-ahead on pushdowns, Determinacy and rewriting of functional top-down and MSO tree transformations, Le théorème de transversale rationnelle dans les langages d'arbres, A new proof of two theorems about rational transductions, Two-way pebble transducers for partial functions and their composition, Decidability of the finiteness of ranges of tree transductions, Top-down tree transducers with deterministic top-down look-ahead, Three hierarchies of transducers, A complete classification of deterministic root-to-frontier tree transformation classes, Output string languages of compositions of deterministic macro tree transducers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Surface tree languages and parallel derivation trees
• Generalized sequential machine maps
• LR-regular grammars - an extension of LR(k) grammars
• Extension of tabled 0L-systems and languages
• Bottom-up and top-down tree transformations— a comparison
• Top-down tree transducers with regular look-ahead
• Mappings and grammars on trees
• Translations on a context free grammar
• A remark on finite transducers