Definability Results for Top-Down Tree Transducers

Sebastian Maneth, Helmut Seidl, Martin Vu

Publikation: Beitrag in FachzeitschriftArtikelBegutachtung

Abstract

Top-down tree transducers are well established formalism for describing tree translations. Such transducers can be further enhanced with look-ahead allowing them to inspect input subtrees before processing them. Oftentimes it is advantageous to know when the look-ahead can be eliminated and the translation be implemented by a simpler transducer. We show that for a given top-down transducer with look-ahead it is decidable whether or not its translation is definable (1) by a linear deterministic top-down tree transducer or (2) by a tree homomorphism. We present algorithms that construct equivalent such transducers if they exist. Our results also apply to bottom-up transducers as well as compositions of transducers.

OriginalspracheEnglisch
Seiten (von - bis)253-287
Seitenumfang35
FachzeitschriftInternational Journal of Foundations of Computer Science
Jahrgang34
Ausgabenummer2-3
DOIs
PublikationsstatusVeröffentlicht - 1 Feb. 2023

Fingerprint

Untersuchen Sie die Forschungsthemen von „Definability Results for Top-Down Tree Transducers“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren