Survey: Weighted Extended Top-down Tree Transducers Part III — Composition ⋆
---
paper_title: Weighted grammars and Kleene's theorem

paper_content:

Abstract Using regular tree grammars weighted over a semiring, we establish Kleene's theorem in the context of formal tree power series.
---
paper_title: Survey: Weighted Extended Top-down Tree Transducers Part II -- Application in Machine Translation

paper_content:

In this second part of the survey, we present the application of weighted extended top-down tree transducers in machine translation, which is the automatic translation of natural language texts. We present several formal properties that are relevant to machine translation and evaluate the weighted extended top-down tree transducer along those criteria. In addition, we demonstrate how to extract rules for an extended top-down tree transducer from existing linguistic data and how to obtain suitable rule weights automatically from similar information. Overall, the aim of the survey is twofold. It should provide a synopsis that illustrates how theory (tree transducers) and practice (machine translation) interact on this particular example. Secondly, it presents a uniform and simplified treatment of the rule extraction and training algorithms that is accessible to the nonexpert. Additional details can be found in the original results that are referenced throughout the text.
---
paper_title: Semirings and their Applications

paper_content:

Preface. 1. Hemirings and semirings: definitions and examples. 2. Sets and relations with values in a semiring. 3. Building new semirings from old. 4. Some conditions on semirings. 5. Complemented elements in semirings. 6. Ideals in semirings. 7. Prime and semiprime ideals in semirings. 8. Factor semirings. 9. Morphisms of semirings. 10. Kernels of morphisms. 11. Semirings of fractions. 12. Euclidean semirings. 13. Additively-regular semirings. 14. Semimodules over semirings. 15. Factor semimodules. 16. Some constructions for semimodules. 17. Free, projective, and injective semimodules. 18. Localization of semimodules. 19. Linear algebra over a semiring. 20. Partially-ordered semirings. 21. Lattice-ordered semirings. 22. Complete semirings. 23. Complete semimodules. 24. CLO-semirings. 25. Fixed points of affine maps. References. Index of applications. Index of terminology.
---
paper_title: Bottom-up and top-down tree transformations— a comparison

paper_content:

The top-down and bottom-up tree transducer are incomparable with respect to their transformation power. The difference between them is mainly caused by the different order in which they use the facilities of copying and nondeterminism. One can however define certain simple tree transformations, independent of the top-down/bottom-up distinction, such that each tree transformation, top-down or bottom-up, can be decomposed into a number of these simple transformations. This decomposition result is used to give simple proofs of composition results concerning bottom-up tree transformations. ::: ::: A new tree transformation model is introduced which generalizes both the top-down and the bottom-up tree transducer.
---
paper_title: The Power of Tree Series Transducers

paper_content:

It is proposed to adjust components, tools and devices of a packaging machine to various formats in accordance with the products to be packaged and packaging material to be used. To assure that the operator will approach the correct conversion point when adjusting the individual conversion points in accordance with a program of a data-processing control unit, the various conversion points have code carriers with a code identifying the particular conversion point. The control unit does not emit an adjusting signal unitl the operator has connected a code reader with the code carrier the code of which agrees with the conversion point displayed at the control unit.
---
paper_title: Compositions of Tree Series Transformations

paper_content:

Tree series transformations computed by bottom-up and top-down tree series transducers are called bottom-up and top-down tree series transformations, respectively. (Functional) compositions of such transformations are investigated. It turns out that the class of bottom-up tree series transformations over a commutative and complete semiring is closed under left-composition with linear bottom-up tree series transformations and right-composition with boolean deterministic bottom-up tree series transformations. ::: ::: Moreover, it is shown that the class of top-down tree series transformations over a commutative and complete semiring is closed under right-composition with linear, nondeleting top-down tree series transformations. Finally, the composition of a boolean, deterministic, total top-down tree series transformation with a linear top-down tree series transformation is shown to be a top-down tree series transformation.
---
paper_title: Bottom-up and Top-down Tree Series Transformations

paper_content:

We generalize bottom-up tree transducers and top-down tree transducers to the concept of bottom-up tree series transducer and top-down tree series transducer, respectively, by allowing formal tree series as output rather than trees, where a formal tree series is a mapping from output trees to some semiring. We associate two semantics with a tree series transducer: a mapping which transforms trees into tree series (for short: tree to tree series transformation or t-ts transformation), and a mapping which transforms tree series into tree series (for short: tree series transformation or ts-ts transformation).We show that the standard case of tree transducers is reobtained by choosing the boolean semiring under the t-ts semantics. Moreover, we show that certain fundamental constructions and results concerning bottom-up and top-down tree transducers can be generalized for the corresponding tree series transducers. Among others, we prove that polynomial bottom-up t-ts transformations can be characterized by the composition of finite state relabeling t-ts transformations and boolean homomorphism t-ts transformations. Moreover, we prove that every deterministic top-down t-ts transformation can be characterized by the composition of a boolean homomorphism t-ts transformation and a deterministic linear top-down t-ts transformation. We prove that deterministic top-down t-ts transformations are closed under right composition with nondeleting and linear deterministic top-down t-ts transformations and are closed under left composition with boolean and total deterministic top-down t-ts transformations. Finally we show that nondeleting linear bottom-up and nondeleting linear top-down tree series transducers generate the same t-ts transformation class.
---
paper_title: C.: Recognizable formal power series on trees

paper_content:

Trees are a very basic object in computer science. They intervene in nearly a;ly domain, and they are studied for their own, or used to represent conveniently a given situation. There are at least three directions where investigations on trees themselves are motivated, and this for different reasons. First, the notion of tree is the basis of algebraic semantics (Nivat [19], Rosen [2*2], etc.). In this context, the study of special languages of trees (i.e. forests), their classification, and their behaviour under various types of transformations are of great importance (Arnold fl], Dauchet [8 J, L,ilin 1161, Mongy [18]). By essence, work in this area is an extension of the algebraic theory of languages; trees and ianguages are in fact directly related via the derivation trees of an algebraic grammar (Thatcher [25]). A second topic heavily related to trees concerns dzra structures, Trees, mainly binary trees &and its variants, constitute one of the most widely known data structures (see e.g. Hlnuth [15]). The analysis of the worst-caLe, expected or average running time t)ehzvGrr nfi’ certain algorithms requires sometimes long and delicate computations (Flajolet [lo], Kemp [14], Flajolet and Steyaert [12]). Finally, trees occupy a distinguished place in the enumeration of graphs and maps, both because of the simplicity of their structure and for the relationship between their el-lcodings and aigebraic languages. The nature of the enumerating series, and especially the question whether they are algebraic or not, is one of the central problems in this domain (Cori [7], Chottin [4]). We propose here a theory of formal power series on trees, and present some of their basic properties together with various examples of applications which, as we hope, will show the interest of its development within the framework we just sketched. A formal power series on trees is a function which Gssociates a number to esch tree. Thus we could also have called them ‘tree functions II in analogy with the term ‘word function’ used by several authors (Paz and Salomaa [ZO], Cobham [5]) as an equivalent denomination for formal power series on words. The main goal of a formal power series is to count, or to represent the result of some computation on
---
paper_title: Benefits of Tree Transducers for Optimizing Functional Programs

paper_content:

We present a technique to prevent the construction of intermediate data structures in functional programs, which is based on results from the theory of tree transducers. We first decompose function definitions, which correspond to macro tree transducers, into smaller pieces. Under certain restrictions these pieces can be composed to an attributed tree transducer using a composition result for attribute grammars. The same construction can be used to compose the attributed tree transducers, which represent the initial function definitions.
---
paper_title: Weighted Tree Automata and Tree Transducers

paper_content:

We survey some important results for weighted tree automata and weighted tree transducers over finite ranked trees and semirings as weight structure. In particular, we address closure properties of the class of recognizable tree series, results on the support of such tree series, the determinization of weighted tree automata, pumping lemmata and decidability results, and finite algebraic characterizations of recognizable tree series. We discuss the equivalence between recognizable tree series and equational, rational, and MSO-definable tree series, and we present a comparison of several other models of recognizability. For weighted tree transducers we show composition and decomposition results, an inclusion diagram of some fundamental classes of tree series transformations, and hierarchies obtained by composing weighted tree transducers. We also discuss other models of weighted tree transducers.
---
paper_title: A Decoder For Syntax-Based Statistical MT

paper_content:

This paper describes a decoding algorithm for a syntax-based translation model (Yamada and Knight, 2001). The model has been extended to incorporate phrasal translations as presented here. In contrast to a conventional word-to-word statistical model, a decoder for the syntax-based model builds up an English parse tree given a sentence in a foreign language. As the model size becomes huge in a practical setting, and the decoder considers multiple syntactic structures for each word alignment, several pruning techniques are necessary. We tested our decoder in a Chinese-to-English translation system, and obtained better results than IBM Model 4. We also discuss issues concerning the relation between this decoder and a language model.
---
paper_title: Composition of top-down and bottom-up tree transductions

paper_content:

Two classes of tree transducers (finite-state automata which read trees and output trees) are studied: “top-down” transducers, which read trees from the root toward the leaves, and “bottom-up” transducers, which read trees from the leaves toward the root. The closure properties of each class under composition are investigated, and some decomposition theorems are presented. It is shown that the two classes can be decomposed into the same two simple classes of transductions. Consequently, for every n , the composition of n transductions in one direction can always be realized by the composition of n + 1 transductions in the other direction. Finally, some results are presented concerning the role of the finite-state control in tree transductions.
---
paper_title: Statistical Phrase-Based Translation

paper_content:

We propose a new phrase-based translation model and decoding algorithm that enables us to evaluate and compare several, previously proposed phrase-based translation models. Within our framework, we carry out a large number of experiments to understand better and explain why phrase-based models out-perform word-based models. Our empirical results, which hold for all examined language pairs, suggest that the highest levels of performance can be obtained through relatively simple means: heuristic learning of phrase translations from word-based alignments and lexical weighting of phrase translations. Surprisingly, learning phrases longer than three words and learning phrases from high-accuracy word-level alignment models does not have a strong impact on performance. Learning only syntactically motivated phrases degrades the performance of our systems.
---
paper_title: Statistical machine translation

paper_content:

This introductory text to statistical machine translation (SMT) provides all of the theories and methods needed to build a statistical machine translator, such as Google Language Tools and Babelfish. In general, statistical techniques allow automatic translation systems to be built quickly for any language-pair using only translated texts and generic software. With increasing globalization, statistical machine translation will be central to communication and commerce. Based on courses and tutorials, and classroom-tested globally, it is ideal for instruction or self-study, for advanced undergraduates and graduate students in computer science and/or computational linguistics, and researchers in natural language processing. The companion website provides open-source corpora and tool-kits.
---
paper_title: Tree Series Transformations that Respect Copying

paper_content:

We consider tree series transducers which were introduced in [EFV], and define the tree-to-tree series transformations computed by them in two different ways. One of the definitions is based on the ←-substitution of tree series taken from [EFV] while the other one is based on a new tree series substitution introduced in this paper. This new substitution is called Open image in new window -substitution and the main difference between the ←- and the Open image in new window -substitutions is that the first one does not take into account the number of the occurrences of the substitution variables while the second one does. We compare the two different ways of computing tree-to-tree series transformations and show that, for the Open image in new window -substitution, fundamental relations from the theory of tree transducers carry over to tree series transducers.
---
paper_title: Efficient Inference through Cascades of Weighted Tree Transducers

paper_content:

Weighted tree transducers have been proposed as useful formal models for representing syntactic natural language processing applications, but there has been little description of inference algorithms for these automata beyond formal foundations. We give a detailed description of algorithms for application of cascades of weighted tree transducers to weighted tree acceptors, connecting formal theory with actual practice. Additionally, we present novel on-the-fly variants of these algorithms, and compare their performance on a syntax machine translation cascade based on (Yamada and Knight, 2001).
---
paper_title: Formal tree series

paper_content:

In this survey we report on generalizations of some results on formal tree languages, tree grammars and tree automata. These generalizations are achieved by an algebraic treatment using semirings, fixed point theory, formal tree series and matrices. By the use of these mathematical constructs definitions, constructions, and proofs are obtained that are very satisfactory from a mathematical point of view. The main surveyed results of the paper are the following: 1. Tree automata (resp. finite, polynomial tree automata), whose behaviours are tree series over a semiring, and systems of equations (resp. finite, polynomial systems of equations), whose least solutions are tuples of tree series over a semiring, are equivalent. 2. A Kleene result: the class of recognizable tree series is characterized by rational tree series expressions. 3. Pushdown tree automata, whose behaviours are tree series over a semiring, and algebraic tree systems are equivalent; moreover, the class of algebraic tree series is characterized by algebraic tree series expressions (a Kleene result). 4. The class of recognizable tree series is closed under nondeterministic simple recognizable tree series transductions. 5. The families of recognizable tree series and of algebraic tree series are full abstract families of tree series (full AFTs). 6. The macro power series, a generalization of the indexed languages, and the algebraic power series are exactly the yields of algebraic tree series and of recognizable tree series, respectively; there is a Kleene result for macro power series; the yield of a full AFT is a full abstract family of power series.
---
paper_title: The Theory of Recognizable Tree Series

paper_content:

The invention is apparatus for laying film in wrinkle-free fashion on a flat surface. A protective film is automatically laid down on a flat rigid vacuum support plate capable of having an image bearing transparency thereon when the instant invention traverses the rigid support plate in one pass in one direction. A photosensitive material and a backing material may then be subsequently supplied to the rigid support plate upon a second pass in the reverse direction to provide a photopolymer plate which may be exposed through a transparency covered by said first film. The resulting photopolymer plate having hardened relief image areas may then be further treated to provide a printing plate.
---
paper_title: Semirings and their Applications

paper_content:

Preface. 1. Hemirings and semirings: definitions and examples. 2. Sets and relations with values in a semiring. 3. Building new semirings from old. 4. Some conditions on semirings. 5. Complemented elements in semirings. 6. Ideals in semirings. 7. Prime and semiprime ideals in semirings. 8. Factor semirings. 9. Morphisms of semirings. 10. Kernels of morphisms. 11. Semirings of fractions. 12. Euclidean semirings. 13. Additively-regular semirings. 14. Semimodules over semirings. 15. Factor semimodules. 16. Some constructions for semimodules. 17. Free, projective, and injective semimodules. 18. Localization of semimodules. 19. Linear algebra over a semiring. 20. Partially-ordered semirings. 21. Lattice-ordered semirings. 22. Complete semirings. 23. Complete semimodules. 24. CLO-semirings. 25. Fixed points of affine maps. References. Index of applications. Index of terminology.
---
paper_title: 2008, ‘The Power of Extended Top-Down Tree Transducers

paper_content:

Extended top-down tree transducers (transducteurs generalises descendants; see [A. Arnold and M. Dauchet, Bi-transductions de forets, in Proceedings of the 3rd International Colloquium on Automata, Languages and Programming, Edinburgh University Press, Edinburgh, 1976, pp. 74-86]) received renewed interest in the field of natural language processing. Here those transducers are extensively and systematically studied. Their main properties are identified and their relation to classical top-down tree transducers is exactly characterized. The obtained properties completely explain the Hasse diagram of the induced classes of tree transformations. In addition, it is shown that most interesting classes of transformations computed by extended top-down tree transducers are not closed under composition.
---
paper_title: Term rewriting and all that

paper_content:

Preface 1. Motivating examples 2. Abstract reduction systems 3. Universal algebra 4. Equational problems 5. Termination 6. Confluence 7. Completion 8. Grobner bases and Buchberger's algorithm 9. Combination problems 10. Equational unification 11. Extensions Appendix 1. Ordered sets Appendix 2. A bluffer's guide to ML Bibliography Index.
---
paper_title: An Overview of Probabilistic Tree Transducers for Natural Language Processing

paper_content:

Probabilistic finite-state string transducers (FSTs) are extremely popular in natural language processing, due to powerful generic methods for applying, composing, and learning them. Unfortunately, FSTs are not a good fit for much of the current work on probabilistic modeling for machine translation, summarization, paraphrasing, and language modeling. These methods operate directly on trees, rather than strings. We show that tree acceptors and tree transducers subsume most of this work, and we discuss algorithms for realizing the same benefits found in probabilistic string transduction.
---
paper_title: 2008, ‘The Power of Extended Top-Down Tree Transducers

paper_content:

Extended top-down tree transducers (transducteurs generalises descendants; see [A. Arnold and M. Dauchet, Bi-transductions de forets, in Proceedings of the 3rd International Colloquium on Automata, Languages and Programming, Edinburgh University Press, Edinburgh, 1976, pp. 74-86]) received renewed interest in the field of natural language processing. Here those transducers are extensively and systematically studied. Their main properties are identified and their relation to classical top-down tree transducers is exactly characterized. The obtained properties completely explain the Hasse diagram of the induced classes of tree transformations. In addition, it is shown that most interesting classes of transformations computed by extended top-down tree transducers are not closed under composition.
---
paper_title: Bottom-up and Top-down Tree Series Transformations

paper_content:

We generalize bottom-up tree transducers and top-down tree transducers to the concept of bottom-up tree series transducer and top-down tree series transducer, respectively, by allowing formal tree series as output rather than trees, where a formal tree series is a mapping from output trees to some semiring. We associate two semantics with a tree series transducer: a mapping which transforms trees into tree series (for short: tree to tree series transformation or t-ts transformation), and a mapping which transforms tree series into tree series (for short: tree series transformation or ts-ts transformation).We show that the standard case of tree transducers is reobtained by choosing the boolean semiring under the t-ts semantics. Moreover, we show that certain fundamental constructions and results concerning bottom-up and top-down tree transducers can be generalized for the corresponding tree series transducers. Among others, we prove that polynomial bottom-up t-ts transformations can be characterized by the composition of finite state relabeling t-ts transformations and boolean homomorphism t-ts transformations. Moreover, we prove that every deterministic top-down t-ts transformation can be characterized by the composition of a boolean homomorphism t-ts transformation and a deterministic linear top-down t-ts transformation. We prove that deterministic top-down t-ts transformations are closed under right composition with nondeleting and linear deterministic top-down t-ts transformations and are closed under left composition with boolean and total deterministic top-down t-ts transformations. Finally we show that nondeleting linear bottom-up and nondeleting linear top-down tree series transducers generate the same t-ts transformation class.
---
paper_title: Top-down tree transducers with regular look-ahead

paper_content:

Top-down tree transducers with regular look-ahead are introduced. It is shown how these can be decomposed and composed, and how this leads to closure properties of surface sets and tree transformation languages. Particular attention is paid to deterministic tree transducers.
---
paper_title: Term rewriting and all that

paper_content:

Preface 1. Motivating examples 2. Abstract reduction systems 3. Universal algebra 4. Equational problems 5. Termination 6. Confluence 7. Completion 8. Grobner bases and Buchberger's algorithm 9. Combination problems 10. Equational unification 11. Extensions Appendix 1. Ordered sets Appendix 2. A bluffer's guide to ML Bibliography Index.
---
paper_title: Survey: Weighted Extended Top-down Tree Transducers Part II -- Application in Machine Translation

paper_content:

In this second part of the survey, we present the application of weighted extended top-down tree transducers in machine translation, which is the automatic translation of natural language texts. We present several formal properties that are relevant to machine translation and evaluate the weighted extended top-down tree transducer along those criteria. In addition, we demonstrate how to extract rules for an extended top-down tree transducer from existing linguistic data and how to obtain suitable rule weights automatically from similar information. Overall, the aim of the survey is twofold. It should provide a synopsis that illustrates how theory (tree transducers) and practice (machine translation) interact on this particular example. Secondly, it presents a uniform and simplified treatment of the rule extraction and training algorithms that is accessible to the nonexpert. Additional details can be found in the original results that are referenced throughout the text.
---
paper_title: Semirings and their Applications

paper_content:

Preface. 1. Hemirings and semirings: definitions and examples. 2. Sets and relations with values in a semiring. 3. Building new semirings from old. 4. Some conditions on semirings. 5. Complemented elements in semirings. 6. Ideals in semirings. 7. Prime and semiprime ideals in semirings. 8. Factor semirings. 9. Morphisms of semirings. 10. Kernels of morphisms. 11. Semirings of fractions. 12. Euclidean semirings. 13. Additively-regular semirings. 14. Semimodules over semirings. 15. Factor semimodules. 16. Some constructions for semimodules. 17. Free, projective, and injective semimodules. 18. Localization of semimodules. 19. Linear algebra over a semiring. 20. Partially-ordered semirings. 21. Lattice-ordered semirings. 22. Complete semirings. 23. Complete semimodules. 24. CLO-semirings. 25. Fixed points of affine maps. References. Index of applications. Index of terminology.
---
paper_title: Bottom-up and top-down tree transformations— a comparison

paper_content:

The top-down and bottom-up tree transducer are incomparable with respect to their transformation power. The difference between them is mainly caused by the different order in which they use the facilities of copying and nondeterminism. One can however define certain simple tree transformations, independent of the top-down/bottom-up distinction, such that each tree transformation, top-down or bottom-up, can be decomposed into a number of these simple transformations. This decomposition result is used to give simple proofs of composition results concerning bottom-up tree transformations. ::: ::: A new tree transformation model is introduced which generalizes both the top-down and the bottom-up tree transducer.
---
paper_title: The Power of Tree Series Transducers

paper_content:

It is proposed to adjust components, tools and devices of a packaging machine to various formats in accordance with the products to be packaged and packaging material to be used. To assure that the operator will approach the correct conversion point when adjusting the individual conversion points in accordance with a program of a data-processing control unit, the various conversion points have code carriers with a code identifying the particular conversion point. The control unit does not emit an adjusting signal unitl the operator has connected a code reader with the code carrier the code of which agrees with the conversion point displayed at the control unit.
---
paper_title: Compositions of Tree Series Transformations

paper_content:

Tree series transformations computed by bottom-up and top-down tree series transducers are called bottom-up and top-down tree series transformations, respectively. (Functional) compositions of such transformations are investigated. It turns out that the class of bottom-up tree series transformations over a commutative and complete semiring is closed under left-composition with linear bottom-up tree series transformations and right-composition with boolean deterministic bottom-up tree series transformations. ::: ::: Moreover, it is shown that the class of top-down tree series transformations over a commutative and complete semiring is closed under right-composition with linear, nondeleting top-down tree series transformations. Finally, the composition of a boolean, deterministic, total top-down tree series transformation with a linear top-down tree series transformation is shown to be a top-down tree series transformation.
---
paper_title: Bottom-up and Top-down Tree Series Transformations

paper_content:

We generalize bottom-up tree transducers and top-down tree transducers to the concept of bottom-up tree series transducer and top-down tree series transducer, respectively, by allowing formal tree series as output rather than trees, where a formal tree series is a mapping from output trees to some semiring. We associate two semantics with a tree series transducer: a mapping which transforms trees into tree series (for short: tree to tree series transformation or t-ts transformation), and a mapping which transforms tree series into tree series (for short: tree series transformation or ts-ts transformation).We show that the standard case of tree transducers is reobtained by choosing the boolean semiring under the t-ts semantics. Moreover, we show that certain fundamental constructions and results concerning bottom-up and top-down tree transducers can be generalized for the corresponding tree series transducers. Among others, we prove that polynomial bottom-up t-ts transformations can be characterized by the composition of finite state relabeling t-ts transformations and boolean homomorphism t-ts transformations. Moreover, we prove that every deterministic top-down t-ts transformation can be characterized by the composition of a boolean homomorphism t-ts transformation and a deterministic linear top-down t-ts transformation. We prove that deterministic top-down t-ts transformations are closed under right composition with nondeleting and linear deterministic top-down t-ts transformations and are closed under left composition with boolean and total deterministic top-down t-ts transformations. Finally we show that nondeleting linear bottom-up and nondeleting linear top-down tree series transducers generate the same t-ts transformation class.
---
paper_title: Weighted Tree Automata and Tree Transducers

paper_content:

We survey some important results for weighted tree automata and weighted tree transducers over finite ranked trees and semirings as weight structure. In particular, we address closure properties of the class of recognizable tree series, results on the support of such tree series, the determinization of weighted tree automata, pumping lemmata and decidability results, and finite algebraic characterizations of recognizable tree series. We discuss the equivalence between recognizable tree series and equational, rational, and MSO-definable tree series, and we present a comparison of several other models of recognizability. For weighted tree transducers we show composition and decomposition results, an inclusion diagram of some fundamental classes of tree series transformations, and hierarchies obtained by composing weighted tree transducers. We also discuss other models of weighted tree transducers.
---
paper_title: Top-down tree transducers with regular look-ahead

paper_content:

Top-down tree transducers with regular look-ahead are introduced. It is shown how these can be decomposed and composed, and how this leads to closure properties of surface sets and tree transformation languages. Particular attention is paid to deterministic tree transducers.
---
paper_title: Composition of top-down and bottom-up tree transductions

paper_content:

Two classes of tree transducers (finite-state automata which read trees and output trees) are studied: “top-down” transducers, which read trees from the root toward the leaves, and “bottom-up” transducers, which read trees from the leaves toward the root. The closure properties of each class under composition are investigated, and some decomposition theorems are presented. It is shown that the two classes can be decomposed into the same two simple classes of transductions. Consequently, for every n , the composition of n transductions in one direction can always be realized by the composition of n + 1 transductions in the other direction. Finally, some results are presented concerning the role of the finite-state control in tree transductions.
---
paper_title: Tree Series Transformations that Respect Copying

paper_content:

We consider tree series transducers which were introduced in [EFV], and define the tree-to-tree series transformations computed by them in two different ways. One of the definitions is based on the ←-substitution of tree series taken from [EFV] while the other one is based on a new tree series substitution introduced in this paper. This new substitution is called Open image in new window -substitution and the main difference between the ←- and the Open image in new window -substitutions is that the first one does not take into account the number of the occurrences of the substitution variables while the second one does. We compare the two different ways of computing tree-to-tree series transformations and show that, for the Open image in new window -substitution, fundamental relations from the theory of tree transducers carry over to tree series transducers.
---
paper_title: Bottom-up and top-down tree transformations— a comparison

paper_content:

The top-down and bottom-up tree transducer are incomparable with respect to their transformation power. The difference between them is mainly caused by the different order in which they use the facilities of copying and nondeterminism. One can however define certain simple tree transformations, independent of the top-down/bottom-up distinction, such that each tree transformation, top-down or bottom-up, can be decomposed into a number of these simple transformations. This decomposition result is used to give simple proofs of composition results concerning bottom-up tree transformations. ::: ::: A new tree transformation model is introduced which generalizes both the top-down and the bottom-up tree transducer.
---
paper_title: Composition of top-down and bottom-up tree transductions

paper_content:

Two classes of tree transducers (finite-state automata which read trees and output trees) are studied: “top-down” transducers, which read trees from the root toward the leaves, and “bottom-up” transducers, which read trees from the leaves toward the root. The closure properties of each class under composition are investigated, and some decomposition theorems are presented. It is shown that the two classes can be decomposed into the same two simple classes of transductions. Consequently, for every n , the composition of n transductions in one direction can always be realized by the composition of n + 1 transductions in the other direction. Finally, some results are presented concerning the role of the finite-state control in tree transductions.
---
paper_title: Bottom-up and top-down tree transformations— a comparison

paper_content:

The top-down and bottom-up tree transducer are incomparable with respect to their transformation power. The difference between them is mainly caused by the different order in which they use the facilities of copying and nondeterminism. One can however define certain simple tree transformations, independent of the top-down/bottom-up distinction, such that each tree transformation, top-down or bottom-up, can be decomposed into a number of these simple transformations. This decomposition result is used to give simple proofs of composition results concerning bottom-up tree transformations. ::: ::: A new tree transformation model is introduced which generalizes both the top-down and the bottom-up tree transducer.
---
paper_title: 2008, ‘The Power of Extended Top-Down Tree Transducers

paper_content:

Extended top-down tree transducers (transducteurs generalises descendants; see [A. Arnold and M. Dauchet, Bi-transductions de forets, in Proceedings of the 3rd International Colloquium on Automata, Languages and Programming, Edinburgh University Press, Edinburgh, 1976, pp. 74-86]) received renewed interest in the field of natural language processing. Here those transducers are extensively and systematically studied. Their main properties are identified and their relation to classical top-down tree transducers is exactly characterized. The obtained properties completely explain the Hasse diagram of the induced classes of tree transformations. In addition, it is shown that most interesting classes of transformations computed by extended top-down tree transducers are not closed under composition.
---
paper_title: On Rational Series and Rational Languages

paper_content:

We study the connections between rational series with coefficients in a semiring and their languages.
---
paper_title: Composition of top-down and bottom-up tree transductions

paper_content:

Two classes of tree transducers (finite-state automata which read trees and output trees) are studied: “top-down” transducers, which read trees from the root toward the leaves, and “bottom-up” transducers, which read trees from the leaves toward the root. The closure properties of each class under composition are investigated, and some decomposition theorems are presented. It is shown that the two classes can be decomposed into the same two simple classes of transductions. Consequently, for every n , the composition of n transductions in one direction can always be realized by the composition of n + 1 transductions in the other direction. Finally, some results are presented concerning the role of the finite-state control in tree transductions.
---
paper_title: Tree Series Transformations that Respect Copying

paper_content:

We consider tree series transducers which were introduced in [EFV], and define the tree-to-tree series transformations computed by them in two different ways. One of the definitions is based on the ←-substitution of tree series taken from [EFV] while the other one is based on a new tree series substitution introduced in this paper. This new substitution is called Open image in new window -substitution and the main difference between the ←- and the Open image in new window -substitutions is that the first one does not take into account the number of the occurrences of the substitution variables while the second one does. We compare the two different ways of computing tree-to-tree series transformations and show that, for the Open image in new window -substitution, fundamental relations from the theory of tree transducers carry over to tree series transducers.
---
paper_title: Full Abstract Families of Tree Series I

paper_content:

We introduce full abstract families of tree series and show that their yields form full abstract families of power series that are closed under algebraic transductions. In the language case, the yield of a full abstract family of tree languages forms a full abstract family of languages that is closed under context-free substitutions.
---
paper_title: Compositions of Tree Series Transformations

paper_content:

Tree series transformations computed by bottom-up and top-down tree series transducers are called bottom-up and top-down tree series transformations, respectively. (Functional) compositions of such transformations are investigated. It turns out that the class of bottom-up tree series transformations over a commutative and complete semiring is closed under left-composition with linear bottom-up tree series transformations and right-composition with boolean deterministic bottom-up tree series transformations. ::: ::: Moreover, it is shown that the class of top-down tree series transformations over a commutative and complete semiring is closed under right-composition with linear, nondeleting top-down tree series transformations. Finally, the composition of a boolean, deterministic, total top-down tree series transformation with a linear top-down tree series transformation is shown to be a top-down tree series transformation.
---
paper_title: Bottom-up and Top-down Tree Series Transformations

paper_content:

We generalize bottom-up tree transducers and top-down tree transducers to the concept of bottom-up tree series transducer and top-down tree series transducer, respectively, by allowing formal tree series as output rather than trees, where a formal tree series is a mapping from output trees to some semiring. We associate two semantics with a tree series transducer: a mapping which transforms trees into tree series (for short: tree to tree series transformation or t-ts transformation), and a mapping which transforms tree series into tree series (for short: tree series transformation or ts-ts transformation).We show that the standard case of tree transducers is reobtained by choosing the boolean semiring under the t-ts semantics. Moreover, we show that certain fundamental constructions and results concerning bottom-up and top-down tree transducers can be generalized for the corresponding tree series transducers. Among others, we prove that polynomial bottom-up t-ts transformations can be characterized by the composition of finite state relabeling t-ts transformations and boolean homomorphism t-ts transformations. Moreover, we prove that every deterministic top-down t-ts transformation can be characterized by the composition of a boolean homomorphism t-ts transformation and a deterministic linear top-down t-ts transformation. We prove that deterministic top-down t-ts transformations are closed under right composition with nondeleting and linear deterministic top-down t-ts transformations and are closed under left composition with boolean and total deterministic top-down t-ts transformations. Finally we show that nondeleting linear bottom-up and nondeleting linear top-down tree series transducers generate the same t-ts transformation class.
---
paper_title: Weighted Tree Automata and Tree Transducers

paper_content:

We survey some important results for weighted tree automata and weighted tree transducers over finite ranked trees and semirings as weight structure. In particular, we address closure properties of the class of recognizable tree series, results on the support of such tree series, the determinization of weighted tree automata, pumping lemmata and decidability results, and finite algebraic characterizations of recognizable tree series. We discuss the equivalence between recognizable tree series and equational, rational, and MSO-definable tree series, and we present a comparison of several other models of recognizability. For weighted tree transducers we show composition and decomposition results, an inclusion diagram of some fundamental classes of tree series transformations, and hierarchies obtained by composing weighted tree transducers. We also discuss other models of weighted tree transducers.
---
paper_title: Bottom-up and top-down tree transformations— a comparison

paper_content:

The top-down and bottom-up tree transducer are incomparable with respect to their transformation power. The difference between them is mainly caused by the different order in which they use the facilities of copying and nondeterminism. One can however define certain simple tree transformations, independent of the top-down/bottom-up distinction, such that each tree transformation, top-down or bottom-up, can be decomposed into a number of these simple transformations. This decomposition result is used to give simple proofs of composition results concerning bottom-up tree transformations. ::: ::: A new tree transformation model is introduced which generalizes both the top-down and the bottom-up tree transducer.
---
paper_title: The Power of Tree Series Transducers

paper_content:

It is proposed to adjust components, tools and devices of a packaging machine to various formats in accordance with the products to be packaged and packaging material to be used. To assure that the operator will approach the correct conversion point when adjusting the individual conversion points in accordance with a program of a data-processing control unit, the various conversion points have code carriers with a code identifying the particular conversion point. The control unit does not emit an adjusting signal unitl the operator has connected a code reader with the code carrier the code of which agrees with the conversion point displayed at the control unit.
---
paper_title: Compositions of Tree Series Transformations

paper_content:

Tree series transformations computed by bottom-up and top-down tree series transducers are called bottom-up and top-down tree series transformations, respectively. (Functional) compositions of such transformations are investigated. It turns out that the class of bottom-up tree series transformations over a commutative and complete semiring is closed under left-composition with linear bottom-up tree series transformations and right-composition with boolean deterministic bottom-up tree series transformations. ::: ::: Moreover, it is shown that the class of top-down tree series transformations over a commutative and complete semiring is closed under right-composition with linear, nondeleting top-down tree series transformations. Finally, the composition of a boolean, deterministic, total top-down tree series transformation with a linear top-down tree series transformation is shown to be a top-down tree series transformation.
---
paper_title: Bottom-up and Top-down Tree Series Transformations

paper_content:

We generalize bottom-up tree transducers and top-down tree transducers to the concept of bottom-up tree series transducer and top-down tree series transducer, respectively, by allowing formal tree series as output rather than trees, where a formal tree series is a mapping from output trees to some semiring. We associate two semantics with a tree series transducer: a mapping which transforms trees into tree series (for short: tree to tree series transformation or t-ts transformation), and a mapping which transforms tree series into tree series (for short: tree series transformation or ts-ts transformation).We show that the standard case of tree transducers is reobtained by choosing the boolean semiring under the t-ts semantics. Moreover, we show that certain fundamental constructions and results concerning bottom-up and top-down tree transducers can be generalized for the corresponding tree series transducers. Among others, we prove that polynomial bottom-up t-ts transformations can be characterized by the composition of finite state relabeling t-ts transformations and boolean homomorphism t-ts transformations. Moreover, we prove that every deterministic top-down t-ts transformation can be characterized by the composition of a boolean homomorphism t-ts transformation and a deterministic linear top-down t-ts transformation. We prove that deterministic top-down t-ts transformations are closed under right composition with nondeleting and linear deterministic top-down t-ts transformations and are closed under left composition with boolean and total deterministic top-down t-ts transformations. Finally we show that nondeleting linear bottom-up and nondeleting linear top-down tree series transducers generate the same t-ts transformation class.
---
paper_title: Composition of top-down and bottom-up tree transductions

paper_content:

Two classes of tree transducers (finite-state automata which read trees and output trees) are studied: “top-down” transducers, which read trees from the root toward the leaves, and “bottom-up” transducers, which read trees from the leaves toward the root. The closure properties of each class under composition are investigated, and some decomposition theorems are presented. It is shown that the two classes can be decomposed into the same two simple classes of transductions. Consequently, for every n , the composition of n transductions in one direction can always be realized by the composition of n + 1 transductions in the other direction. Finally, some results are presented concerning the role of the finite-state control in tree transductions.
---
paper_title: Bottom-up and Top-down Tree Series Transformations

paper_content:

We generalize bottom-up tree transducers and top-down tree transducers to the concept of bottom-up tree series transducer and top-down tree series transducer, respectively, by allowing formal tree series as output rather than trees, where a formal tree series is a mapping from output trees to some semiring. We associate two semantics with a tree series transducer: a mapping which transforms trees into tree series (for short: tree to tree series transformation or t-ts transformation), and a mapping which transforms tree series into tree series (for short: tree series transformation or ts-ts transformation).We show that the standard case of tree transducers is reobtained by choosing the boolean semiring under the t-ts semantics. Moreover, we show that certain fundamental constructions and results concerning bottom-up and top-down tree transducers can be generalized for the corresponding tree series transducers. Among others, we prove that polynomial bottom-up t-ts transformations can be characterized by the composition of finite state relabeling t-ts transformations and boolean homomorphism t-ts transformations. Moreover, we prove that every deterministic top-down t-ts transformation can be characterized by the composition of a boolean homomorphism t-ts transformation and a deterministic linear top-down t-ts transformation. We prove that deterministic top-down t-ts transformations are closed under right composition with nondeleting and linear deterministic top-down t-ts transformations and are closed under left composition with boolean and total deterministic top-down t-ts transformations. Finally we show that nondeleting linear bottom-up and nondeleting linear top-down tree series transducers generate the same t-ts transformation class.
---

Title: Survey: Weighted Extended Top-down Tree Transducers Part III — Composition ⋆

Section 1: Motivation
Description 1: This section explains the motivation behind studying the compositions of weighted extended top-down tree transducers and provides context about the importance and applications of these studies.

Section 2: Notation
Description 2: This section introduces the notations and basic definitions used throughout the paper, including sets, alphabets, trees, and semirings.

Section 3: An Example Composition
Description 3: This section presents an example to illustrate the problem of composition with weighted extended top-down tree transducers and the general principles used to solve it.

Section 4: An Equivalent Model
Description 4: This section introduces an alternative model for weighted extended top-down tree transducers with explicit rule identifiers and discusses its benefits for composition constructions.

Section 5: Composition with a Top-down Tree Transducer
Description 5: This section discusses the composition of a weighted extended top-down tree transducer with a top-down tree transducer, presenting the generic composition construction and analyzing its correctness.

Section 6: Allowing ε-rules
Description 6: This section investigates the impact of ε-rules in the composition of tree transformations and extends the results to the weighted setting, highlighting differences and new findings.