Equivalence of Deterministic Nested Word to Word Transducers

Slawomir Staworko; Grégoire Laurence; Aurélien Lemay; Joachim Niehren

doi:10.1007/978-3-642-03409-1_28

Equivalence of Deterministic Nested Word to Word Transducers

Slawomir Staworko, Grégoire Laurence, Aurélien Lemay, Joachim Niehren

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English
Title of host publication	Fundamentals of Computation Theory
Subtitle of host publication	17th International Symposium, FCT 2009, Wroclaw, Poland, September 2-4, 2009. Proceedings
Publisher	Springer Berlin Heidelberg
Pages	310-322
Number of pages	13
Volume	5699
ISBN (Electronic)	978-3-642-03409-1
ISBN (Print)	978-3-642-03408-4
DOIs	https://doi.org/10.1007/978-3-642-03409-1_28
Publication status	Published - 2009

Access to Document

10.1007/978-3-642-03409-1_28

Staworko Laurence ET AL 2009 Equivalence of Deterministic Nested Word to Word TransducersAccepted author manuscript, 220 KB

http://dx.doi.org/10.1007/978-3-642-03409-1_28

Cite this

@inproceedings{acb072854e5f40898ad62b7511c07901,

title = "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.",

author = "Slawomir Staworko and Gr{\'e}goire Laurence and Aur{\'e}lien Lemay and Joachim Niehren",

year = "2009",

doi = "10.1007/978-3-642-03409-1_28",

language = "English",

isbn = "978-3-642-03408-4",

volume = "5699",

pages = "310--322",

booktitle = "Fundamentals of Computation Theory",

publisher = "Springer Berlin Heidelberg",

}

Equivalence of Deterministic Nested Word to Word Transducers. / Staworko, Slawomir; Laurence, Grégoire; Lemay, Aurélien; Niehren, Joachim.

Fundamentals of Computation Theory: 17th International Symposium, FCT 2009, Wroclaw, Poland, September 2-4, 2009. Proceedings. Vol. 5699 Springer Berlin Heidelberg, 2009. p. 310-322.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Equivalence of Deterministic Nested Word to Word Transducers

AU - Staworko, Slawomir

AU - Laurence, Grégoire

AU - Lemay, Aurélien

AU - Niehren, Joachim

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-642-03409-1_28

DO - 10.1007/978-3-642-03409-1_28

M3 - Conference contribution

SN - 978-3-642-03408-4

VL - 5699

SP - 310

EP - 322

BT - Fundamentals of Computation Theory

PB - Springer Berlin Heidelberg

ER -

Equivalence of Deterministic Nested Word to Word Transducers

Abstract

Access to Document

Fingerprint

Cite this