Decision problems of tree transducers with origin

DOI10.1016/j.ic.2018.02.011zbMath1396.68065OpenAlexW2796150747MaRDI QIDQ1641005

Emmanuel Filiot, Pierre-Alain Reynier, Jean-Marc Talbot, Sebastian Maneth

Publication date: 14 June 2018

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2018.02.011

zbMATH Keywords

equivalenceinjectivitymonadic second-order logicdecidabilitytop-down tree transducermacro tree transducerorigin informationsubclass definability

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Related Items

Deciding origin equivalence of weakly self-nesting macro tree transducers, Deciding whether an attributed translation can be realized by a top-down transducer, One-way resynchronizability of word transducers, Origin-equivalence of two-way word transducers is in PSPACE

Cites Work

• Unnamed Item
• Unnamed Item
• The equivalence problem for deterministic MSO tree transducers is decidable
• Look-ahead removal for total deterministic top-down tree transducers
• Macro tree transducers
• The equivalence of finite valued transducers (on HDT0L languages) is decidable
• Tree transducers, L systems, and two-way machines
• On tree transducers for partial functions
• Decidability of the finiteness of ranges of tree transductions
• On the equivalence problem for letter-to-letter top-down tree transducers
• On injectivity of deterministic top-down tree transducers
• Origin tracking
• Typechecking for XML transformers
• A comparison of tree transductions defined by monadic second order logic and by attribute grammars
• Macro tree transducers, attribute grammars, and MSO definable tree translations.
• Transducer-based analysis of cryptographic protocols
• Generalized sequential machine maps
• Linking theorems for tree transducers
• Determinacy and Rewriting of Top-Down and MSO Tree Transformations
• Tree Transformations and Dependencies
• On the equivalence problem for attribute systems
• Decision Problems of Tree Transducers with Origin
• The Power of Extended Top-Down Tree Transducers
• On the Monadic Second-Order Transduction Hierarchy
• The Unsolvability of the Equivalence Problem for $\varepsilon $-Free NGSM’s with Unary Input (Output) Alphabet and Applications
• Macro Tree Translations of Linear Size Increase are MSO Definable
• Composition of functions with accumulating parameters
• Transducers with Origin Information
• Enhancing semantic bidirectionalization via shape bidirectionalizer plug-ins
• The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
• Mappings and grammars on trees