Equivalence of Deterministic Nested Word to Word Transducers

Abstract : 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.
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/inria-00423961
Contributor : Grégoire Laurence <>
Submitted on : Tuesday, October 13, 2009 - 2:53:24 PM
Last modification on : Thursday, February 21, 2019 - 10:52:49 AM
Long-term archiving on : Tuesday, October 16, 2012 - 12:10:59 PM

File

0.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Slawomir Staworko, Grégoire Laurence, Aurélien Lemay, Joachim Niehren. Equivalence of Deterministic Nested Word to Word Transducers. Fundamentals of Computation Theory, Maciej Gebala and Malgorzata Korzeniowska, Sep 2009, Wroclaw, Poland. pp.310-322, ⟨10.1007/978-3-642-03409-1_28⟩. ⟨inria-00423961⟩

Share

Metrics

Record views

661

Files downloads

356