𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Shape preserving top-down tree transducers

✍ Scribed by Zoltán Fülöp; Zsolt Gazdag

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
377 KB
Volume
304
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

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 a top-down tree transducer is shape preserving if and only if it is equivalent to a top-down relabeling tree transducer. We also prove that it is decidable if a top-down tree transducer is shape preserving.

📜 SIMILAR VOLUMES

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

Top-down decision tree learning as infor
Top-down decision tree learning as information based boosting
✍ Eiji Takimoto; Akira Maruoka 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 180 KB

We consider a boosting technique that can be directly applied to multiclass classiÿcation problems. Although many boosting algorithms have been proposed so far, most of them are developed essentially for binary classiÿcation problems, and in order to handle multiclass classiÿcation problems, they ne

Top-down induction of first-order logica
Top-down induction of first-order logical decision trees
✍ Hendrik Blockeel; Luc De Raedt 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 895 KB

A first-order framework for top-down induction of logical decision trees is introduced. The expressivity of these trees is shown to be larger than that of the flat logic programs which are typically induced by classical ILP systems, and equal to that of first-order decision lists. These results are