Characterizing attributed tree translations in terms of macro tree transducers

DOI10.1016/J.TCS.2023.113943MaRDI QIDQ6104348zbMATH OpenFDO

Authors

Publication date 15 June 2023

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

Full work available at URL https://arxiv.org/abs/2209.07090

zbMATH Keywords

macro tree transducersattributed tree transformations

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: It is well known that attributed tree transducers can be equipped with "regular look-around" in order to obtain a more robust class of translations. We present two characterizations of this class in terms of macro tree transducers (MTTs): the first one is a static restriction on the rules of the MTTs, where the MTTs need to be equipped with regular look-around. The second characterization is a dynamic one, where the MTTs only need regular look-ahead.

Recommendations

• A characterization of attributed tree transformations by a subclass of macro tree transducers
• Characterizing important subclasses of attributed tree transformations by macro tree transducers
• Macro tree transducers, attribute grammars, and MSO definable tree translations.
• Macro tree transducers
• A comparison of tree transductions defined by monadic second order logic and by attribute grammars

Cites work

• scientific article; zbMATH DE number 3740783 (Why is no real title available?)
• scientific article; zbMATH DE number 1200800 (Why is no real title available?)
• scientific article; zbMATH DE number 7561353 (Why is no real title available?)
• A characterization of attributed tree transformations by a subclass of macro tree transducers
• A comparison of pebble tree transducers with macro tree transducers
• A comparison of tree transductions defined by monadic second order logic and by attribute grammars
• Attribute grammars and recursive program schemes. I. II
• Equivalence of deterministic top-down tree-to-string transducers is decidable
• Macro tree transducers
• Macro tree transducers, attribute grammars, and MSO definable tree translations.
• Semantics of context-free languages
• Semantics of context-free languages: Correction
• Typechecking for XML transformers

Cited in

(3)

• scientific article; zbMATH DE number 5506094 (Why is no real title available?)
• scientific article; zbMATH DE number 3866600 (Why is no real title available?)
• Attributed tree transducers for partial functions

This page was built for publication: Characterizing attributed tree translations in terms of macro tree transducers

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