𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On injectivity of deterministic top–down tree transducers

✍ Scribed by Z. Fülöp; P. Gyenizse

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
499 KB
Volume
48
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Shape preserving top-down tree transduce
Shape preserving top-down tree transducers
✍ Zoltán Fülöp; Zsolt Gazdag 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 377 KB

As top-down tree transducers generalize generalized sequential machines, shape preserving top-down tree transducers naturally generalize length preserving generalized sequential machines. For instance, top-down relabeling tree transducers are shape preserving top-down tree transducers. We show that

The Equivalence of Bottom-Up and Top-Dow
The Equivalence of Bottom-Up and Top-Down Tree-to-Graph Transducers
✍ Joost Engelfriet; Heiko Vogler 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 979 KB

We introduce the bottom-up tree-to-graph transducer, which is very similar to the usual (total deterministic) bottom-up tree transducer except that it translates trees into hypergraphs rather than trees, using hypergraph substitution instead of tree substitution. If every output hypergraph of the tr

Output String Languages of Compositions
Output String Languages of Compositions of Deterministic Macro Tree Transducers
✍ Joost Engelfriet; Sebastian Maneth 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 376 KB

The composition of total deterministic macro tree transducers gives rise to a proper hierarchy with respect to their output string languages (these are the languages obtained by taking the yields of the output trees). There is a language not in this hierarchy which can be generated by a (quite restr

On the Boosting Ability of Top–Down Deci
On the Boosting Ability of Top–Down Decision Tree Learning Algorithms
✍ Michael Kearns; Yishay Mansour 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 513 KB

We analyze the performance of top down algorithms for decision tree learning, such as those employed by the widely used C4.5 and CART software packages. Our main result is a proof that such algorithms are boosting algorithms. By this we mean that if the functions that label the internal nodes of the