How to Remove the Look-Ahead of Top-Down Tree Transducers

Joost Engelfriet, Sebastian Maneth, Helmut Seidl

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

For a top-down tree transducer with regular look-ahead we introduce the notion of difference bound, which is a number bounding the difference in output height for any two look-ahead states of the transducer. We present an algorithm that, for a given transducer with a known difference bound, decides whether it is equivalent to a transducer without regular look-ahead, and constructs such a transducer if the answer is positive. All transducers are total and deterministic.
Original languageEnglish
Title of host publicationDevelopments in Language Theory
Subtitle of host publication18th International Conference, DLT 2014, Ekaterinburg, Russia, August 26-29, 2014. Proceedings
PublisherSpringer International Publishing
Number of pages13
ISBN (Electronic)978-3-319-09698-8
ISBN (Print)978-3-319-09697-1
Publication statusPublished - 2014


Dive into the research topics of 'How to Remove the Look-Ahead of Top-Down Tree Transducers'. Together they form a unique fingerprint.

Cite this