IEEE - Institute of Electrical and Electronics Engineers, Inc. - Equivalence of Deterministic Top-Down Tree-to-String Transducers is Decidable

2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS)

Author(s): Helmut Seidl ; Sebastian Maneth ; Gregor Kemper
Publisher: IEEE - Institute of Electrical and Electronics Engineers, Inc.
Publication Date: 1 October 2015
Conference Location: Berkeley, CA, USA
Conference Date: 17 October 2015
Page(s): 943 - 962
ISBN (Electronic): 978-1-4673-8191-8
ISSN (Paper): 0272-5428
DOI: 10.1109/FOCS.2015.62
Regular:

We show that equivalence of deterministic top-down tree-to-string transducers is decidable, thus solving a long standing open problem in formal language theory. We also present efficient... View More

Advertisement