| Autor: |
Staworko, Sławomir, Laurence, Grégoire, Lemay, Aurélien, Niehren, Joachim |
| Zdroj: |
Fundamentals of Computation Theory (9783642034084); 2009, p310-322, 13p |
| Abstrakt: |
We study the equivalence problem of deterministic nested word to word transducers and show it to be surprisingly robust. Modulo polynomial time reductions, it can be identified with 4 equivalence problems for diverse classes of deterministic non-copying order-preserving transducers. In particular, we present polynomial time back and fourth reductions to the morphism equivalence problem on context free languages, which is known to be solvable in polynomial time. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
