Decision problems of tree transducers with origin
type: Item
instance of: scholarly article
title: Decision problems of tree transducers with origin
zbMATH Open document ID: 1396.68065
author: Emmanuel Filiot
author: Sebastian Maneth
author: Pierre-Alain Reynier
author: Jean-Marc Talbot
published in: Information and Computation
publication date: 2018-06-14T00:00:00Z
review text: The contribution discusses decidability results for tree transducers with origin information. The origin information assigns to each output node the corresponding node in the input tree to which the rule creating the output node was applied. It thus provides additional information about the derivation process used to obtain the given input-output pair. The tree transducer models discussed in this contribution include the classical top-down tree-to-tree transducers, the top-down tree-to-string transducers as well as the MSO tree-to-string transducers. These devices traditionally compute relations between input and output only, but in the origin mode they relate input trees to output trees together with their origin information. For this origin semantics the considered decidability questions include equivalence, injectivity, and subclass definability. With the help of the additional origin information several classical undecidable properties become decidable. For example, equivalence and injectivity become decidable for top-down tree transducers as well as for MSO tree-to-string transducers (with origin information). However, these two problems remain undecidable for top-down tree-to-string transducers. The first subclass definability question is whether a given deterministic top-down tree-to-string transducer permits an equivalent (incl. origin) MSO tree-to-string transducer. It is demonstrated that this question is decidable. Similarly, it is decidable under origin-semantics whether a given total deterministic macro tree transducer (i.e., a top-down tree transducer with additional context-parameters) permits an equivalent top-down tree transducer. The same problem remains open for tree transducers in the classical, origin-less, semantics. The paper is well written and easily accessible. Full proof details are provided for all results and examples illustrate the main notions. Graphical illustrations help the reader with suitable visualization, and ample motivation, c…
reviewed by: Andreas Maletti
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 03D05
zbMATH DE Number: 6889860
zbMATH Keywords: top-down tree transducer
zbMATH Keywords: macro tree transducer
zbMATH Keywords: monadic second-order logic
zbMATH Keywords: origin information
zbMATH Keywords: decidability
zbMATH Keywords: equivalence
zbMATH Keywords: injectivity
zbMATH Keywords: subclass definability
MaRDI profile type: Publication
full work available at URL: j.ic.2018.02.011
OpenAlex ID: W2796150747
cites work: On the equivalence problem for letter-to-letter top-down tree transducers
cites work: Determinacy and Rewriting of Top-Down and MSO Tree Transformations
cites work: A comparison of tree transductions defined by monadic second order logic and by attribute grammars
cites work: On the Monadic Second-Order Transduction Hierarchy
cites work: Transducers with Origin Information
cites work: On the equivalence problem for attribute systems
cites work: The equivalence of finite valued transducers (on HDT0L languages) is decidable
cites work: Decidability of the finiteness of ranges of tree transductions
cites work: On tree transducers for partial functions
cites work: Macro tree transducers, attribute grammars, and MSO definable tree translations.
cites work: Macro Tree Translations of Linear Size Increase are MSO Definable
cites work: The equivalence problem for deterministic MSO tree transducers is decidable
cites work: Look-ahead removal for total deterministic top-down tree transducers
cites work: Tree transducers, L systems, and two-way machines
cites work: Macro tree transducers
cites work: Q3906457
cites work: Decision Problems of Tree Transducers with Origin
cites work: On injectivity of deterministic top-down tree transducers
cites work: Linking theorems for tree transducers
cites work: Q4210160
cites work: The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
cites work: The Unsolvability of the Equivalence Problem for $\varepsilon $-Free NGSM’s with Unary Input (Output) Alphabet and Applications
cites work: Transducer-based analysis of cryptographic protocols
cites work: Tree Transformations and Dependencies
cites work: The Power of Extended Top-Down Tree Transducers
cites work: Typechecking for XML transformers
cites work: Mappings and grammars on trees
cites work: Generalized sequential machine maps
cites work: Origin tracking
cites work: Enhancing semantic bidirectionalization via shape bidirectionalizer plug-ins
cites work: Composition of functions with accumulating parameters
DOI: 10.1016/J.IC.2018.02.011
description: scientific article; zbMATH DE number 6889860