TY - GEN
T1 - How to remove the look-ahead of top-down tree transducers
AU - Engelfriet, Joost
AU - Maneth, Sebastian
AU - Seidl, Helmut
PY - 2014
Y1 - 2014
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84958543846&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-09698-8_10
DO - 10.1007/978-3-319-09698-8_10
M3 - Conference contribution
AN - SCOPUS:84958543846
SN - 9783319096971
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 103
EP - 115
BT - Developments in Language Theory - 18th International Conference, DLT 2014, Proceedings
PB - Springer Verlag
T2 - 18th International Conference on Developments in Language Theory, DLT 2014
Y2 - 26 August 2014 through 29 August 2014
ER -