Deciding Equivalence of Linear Tree-to-Word Transducers in Polynomial Time

DOI10.1007/978-3-662-53132-7_29zbMath1436.68162arXiv1606.03758OpenAlexW2424818204MaRDI QIDQ2817401

Raphaela Palenta, Adrien Boiret

Publication date: 30 August 2016

Published in: Developments in Language Theory (Search for Journal in Brave)

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

zbMATH Keywords

partial normal formtree transducerdeciding equivalence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (3)

Equivalence of Linear Tree Transducers with Output in the Free Group ⋮ Unnamed Item ⋮ Streaming ranked-tree-to-string transducers

Cites Work

• The equivalence problem for deterministic MSO tree transducers is decidable
• Deciding equivalence of top-down XML transformations in polynomial time
• Macro tree transducers
• Normal Form on Linear Tree-to-Word Transducers
• Normalization of Sequential Top-Down Tree-to-Word Transducers
• Equivalence of Deterministic Nested Word to Word Transducers
• Macro Tree Translations of Linear Size Increase are MSO Definable
• Tree transducers, L systems and two-way machines (Extended Abstract)
• The Compressed Word Problem for Groups

This page was built for publication: Deciding Equivalence of Linear Tree-to-Word Transducers in Polynomial Time