Equivalence of Deterministic Nested Word to Word Transducers

DOI10.1007/978-3-642-03409-1_28MaRDI QIDQ3183621zbMATH OpenOpenAlexWikidataFDO

Authors Sławomir Staworko, Grégoire Laurence, Aurélien Lemay, Joachim Niehren

Publication date 20 October 2009

Published in Fundamentals of Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-03409-1_28

zbMATH Keywords

automatacontext-free grammarstransducerstreesXML

Mathematics Subject Classification ID

Data structures (68P05) Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Recommendations

• Deciding equivalence of linear tree-to-word transducers in polynomial time
• Equivalence of deterministic top-down tree-to-string transducers is decidable
• Decidability of equivalence for a class of non-deterministic tree transducers
• Equivalence of symbolic tree transducers
• On the equivalence problem for letter-to-letter top-down tree transducers

Cited in

(7)

• Visibly pushdown transducers
• Colored nested words
• Deciding equivalence of linear tree-to-word transducers in polynomial time
• Visibly pushdown transducers with look-ahead
• Equivalence of Linear Tree Transducers with Output in the Free Group
• A uniformization theorem for nested word to word transductions
• Streaming ranked-tree-to-string transducers

This page was built for publication: Equivalence of Deterministic Nested Word to Word Transducers

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