Survey Weighted extended top-down tree transducers part I. : basics and expressive power /

Weighted extended top-down tree transducers (transducteurs généralisés descendants [Arnold, Dauchet: Bi-transductions de forêts. ICALP'76. Edinburgh University Press, 1976]) received renewed interest in the field of Natural Language Processing, where they are used in syntax-based machine transl...

Full description

Saved in:
Bibliographic Details
Main Author: Maletti Andreas
Corporate Author: Weighted Automata : Theory and Applications (2010) (Leipzig)
Format: Article
Published: 2011
Series:Acta cybernetica 20 No. 2
Kulcsszavak:Számítástechnika, Kibernetika
Subjects:
doi:10.14232/actacyb.20.2.2011.2

Online Access:http://acta.bibl.u-szeged.hu/12909
Description
Summary:Weighted extended top-down tree transducers (transducteurs généralisés descendants [Arnold, Dauchet: Bi-transductions de forêts. ICALP'76. Edinburgh University Press, 1976]) received renewed interest in the field of Natural Language Processing, where they are used in syntax-based machine translation. This survey presents the foundations for a theoretical analysis of weighted extended top-down tree transducers. In particular, it discusses essentially complete semirings, which are a novel concept that can be used to lift incomparability results from the unweighted case to the weighted case even in the presence of infinite sums. In addition, several equivalent ways to define weighted extended top-down tree transducers are presented and the individual benefits of each presentation is shown on a small result.
Physical Description:223-250
ISSN:0324-721X