Characterizing attributed tree translations in terms of macro tree transducers

DOI10.1016/J.TCS.2023.113943arXiv2209.07090MaRDI QIDQ6104348FDOQ6104348

Authors:

Publication date: 15 June 2023

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

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.

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

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

zbMATH Keywords

macro tree transducersattributed tree transformations

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

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

Cited In (3)

• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)