Transductions of dags and trees

DOI10.1007/BF01786981zbMATH Open0505.68035MaRDI QIDQ4742320FDOQ4742320

Authors: Tsutomu Kamimura, Giora Slutzki 

Publication date: 1982

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

directed acyclic graphstree languagestransductionsphrase-structure grammarsdag languagesbottom-up dag-to-tree transducers

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Bottom-up and top-down tree transformations— a comparison
• Top-down tree transducers with regular look-ahead
• On the computational power of pushdown automata
• Translations on a context free grammar
• Generalized sequential machine maps
• Mappings and grammars on trees
• Composition of top-down and bottom-up tree transductions
• Tree transducers, L systems, and two-way machines
• Generalized Syntax Directed Translation, Tree Transducers, and Linear Space
• Tree transducers, L systems and two-way machines (Extended Abstract)
• Title not available (Why is that?)
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Algebra automata I: Parallel programming as a prolegomena to the categorical approach
• Acceptors for the derivation languages of phrase-structure grammars
• Title not available (Why is that?)
• Semantic preserving translations
• Title not available (Why is that?)
• On the syntactic structures of unrestricted grammars I. Generative grammars and phrase structure grammars

Cited In (3)

• The ancestor width of grammars and languages
• Graph Automata: The Algebraic Properties of Abelian Relational Graphoids
• Graph automata

This page was built for publication: Transductions of dags and trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4742320)