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

Joost Engelfriet; Sebastian Maneth; Helmut Seidl

doi:10.1007/978-3-319-09698-8_10

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

Joost Engelfriet, Sebastian Maneth, Helmut Seidl

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

Abstract

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 language	English
Title of host publication	Developments in Language Theory
Subtitle of host publication	18th International Conference, DLT 2014, Ekaterinburg, Russia, August 26-29, 2014. Proceedings
Publisher	Springer
Pages	103-115
Number of pages	13
Volume	8633
ISBN (Electronic)	978-3-319-09698-8
ISBN (Print)	978-3-319-09697-1
DOIs	https://doi.org/10.1007/978-3-319-09698-8_10
Publication status	Published - 2014

Access to Document

10.1007/978-3-319-09698-8_10

Engelfriet Maneth ET AL 2014 How to Remove the Look-AheadSubmitted manuscript, 279 KB

http://dx.doi.org/10.1007/978-3-319-09698-8_10

Cite this

@inproceedings{81cc3d7732d148c8aaeff2c55703e9f7,

title = "How to Remove the Look-Ahead of Top-Down Tree Transducers",

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

author = "Joost Engelfriet and Sebastian Maneth and Helmut Seidl",

year = "2014",

doi = "10.1007/978-3-319-09698-8_10",

language = "English",

isbn = "978-3-319-09697-1",

volume = "8633",

pages = "103--115",

booktitle = "Developments in Language Theory",

publisher = "Springer",

address = "United Kingdom",

}

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.

U2 - 10.1007/978-3-319-09698-8_10

DO - 10.1007/978-3-319-09698-8_10

M3 - Conference contribution

SN - 978-3-319-09697-1

VL - 8633

SP - 103

EP - 115

BT - Developments in Language Theory

PB - Springer

ER -

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

Abstract

Access to Document

Fingerprint

Cite this