Functionality of compositions of top-down tree transducers is decidable

DOI10.1016/J.IC.2023.105131OpenAlexW4389778718MaRDI QIDQ6178464FDOQ6178464

Authors: Sebastian Maneth, Helmut Seidl, Martin Vu 

Publication date: 18 January 2024

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

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

zbMATH Keywords

decidabilitytop-down tree transducerfunctionality

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Bottom-up and top-down tree transformations— a comparison
• Top-down tree transducers with regular look-ahead
• Translations on a context free grammar
• Generalized sequential machine maps
• Mappings and grammars on trees
• Composition of top-down and bottom-up tree transductions
• Tree transducers, L systems, and two-way machines
• On tree transducers for partial functions
• Three hierarchies of transducers
• Definability results for top-down tree transducers
• Polynomial-time inverse computation for accumulative functions with multiple data traversals
• Title not available (Why is that?)
• Deciding equivalence of top-down XML transformations in polynomial time
• A survey on decidable equivalence problems for tree transducers
• Grammatical picture generation. A tree-based approach. With CD-ROM.
• Transformations and translations from the point of view of generalized finite automata theory
• How to decide functionality of compositions of top-down tree transducers
• Transducer-based analysis of cryptographic protocols

Cited In (1)

• Attributed tree transducers for partial functions

This page was built for publication: Functionality of compositions of top-down tree transducers is decidable

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