2 papers
cs.FL2019
Deciding Equivalence of Separated Non-Nested Attribute Systems in Polynomial Time
Helmut Seidl, Raphaela Palenta, Sebastian Maneth
In 1982, Courcelle and Franchi-Zannettacci showed that the equivalence problem of separated non-nested attribute systems can be reduced to the equivalence problem of total determin…
cs.FL2016
Deciding Equivalence of Linear Tree-to-Word Transducers in Polynomial Time
Adrien Boiret, Raphaela Palenta
We show that the equivalence of deterministic linear top-down tree-to-word transducers is decidable in polynomial time. Linear tree-to-word transducers are non-copying but not nece…