Hierarchies of tree series transformations

DOI10.1016/J.TCS.2004.01.001MaRDI QIDQ1826640zbMATH OpenOpenAlexFDO

Authors Zoltán Fülöp, Zsolt Gazdag, Heiko Vogler

Publication date 6 August 2004

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2004.01.001

zbMATH Keywords

Tree automataTree series transducersTree transducers

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Review text

We study bottom-up and top-down tree series transducers over a semiring A . We present an inclusion diagram and prove its correctness. This inclusion diagram implies the properness of four hierarchies. As the second main result we prove that the first two hierarchies are proper even for arbitrary (i.e., not necessarily commutative) izz-semirings.

Recommendations

• Hierarchies of Tree Series Transformations Revisited
• scientific article; zbMATH DE number 1809721
• A hierarchy of deterministic top-down tree transformations
• Compositions of tree series transformations
• Hasse diagrams for classes of deterministic bottom-up tree-to-tree-series transformations

Cites work

• Bottom-up and top-down tree transformations— a comparison
• Composition of top-down and bottom-up tree transductions
• Context-free series on trees
• Equational elements in additive algebras
• Generalized sequential machine maps
• scientific article; zbMATH DE number 4016218 (Why is no real title available?)
• scientific article; zbMATH DE number 1809721 (Why is no real title available?)
• scientific article; zbMATH DE number 3854429 (Why is no real title available?)
• scientific article; zbMATH DE number 4041315 (Why is no real title available?)
• scientific article; zbMATH DE number 54244 (Why is no real title available?)
• scientific article; zbMATH DE number 1200800 (Why is no real title available?)
• scientific article; zbMATH DE number 1354999 (Why is no real title available?)
• scientific article; zbMATH DE number 475423 (Why is no real title available?)
• scientific article; zbMATH DE number 475426 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• IO and OI. I
• Mappings and grammars on trees
• Recognizable formal power series on trees
• Three hierarchies of transducers
• Top-down tree transducers with regular look-ahead
• Tree series transformations that respect copying
• Tree transducers, L systems, and two-way machines

Cited in

(14)

• A Kleene theorem for weighted tree automata over distributive multioperator monoids
• Survey: Weighted extended top-down tree transducers. III. Composition
• scientific article; zbMATH DE number 1809721 (Why is no real title available?)
• Tree-Series-to-Tree-Series Transformations
• Hierarchies of Tree Series Transformations Revisited
• DECOMPOSITION OF WEIGHTED MULTIOPERATOR TREE AUTOMATA
• scientific article; zbMATH DE number 2040322 (Why is no real title available?)
• scientific article; zbMATH DE number 1894656 (Why is no real title available?)
• Incomparability results for classes of polynomial tree series transformations
• Hasse diagrams for classes of deterministic bottom-up tree-to-tree-series transformations
• The power of weighted regularity-preserving multi bottom-up tree transducers
• Sequences of trees and higher-order renormalization group equations
• Weighted bottom-up and top-down tree transformations are incomparable
• Compositions of tree series transformations

This page was built for publication: Hierarchies of tree series transformations

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