Equivalence of Deterministic Top-Down Tree-to-String Transducers Is Decidable

DOI10.1145/3182653zbMath1426.68154arXiv1503.09163OpenAlexW2797808503MaRDI QIDQ4561509

Gregor Kemper, Helmut Seidl, Sebastian Maneth

Publication date: 6 December 2018

Published in: Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

decidabilitypolynomial idealsequivalence problemmacro tree transducertree-to-string transducer

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items

Equivalence of Linear Tree Transducers with Output in the Free Group, On the Balancedness of Tree-to-Word Transducers, Deciding origin equivalence of weakly self-nesting macro tree transducers, Characterizing attributed tree translations in terms of macro tree transducers, Unnamed Item, Unnamed Item, Streaming ranked-tree-to-string transducers, Copyful Streaming String Transducers, On the Balancedness of Tree-to-Word Transducers