- AutorIn
- Andreas Maletti
- Titel
- Inclusion Diagrams for Classes of Deterministic Bottom-up Tree-to-Tree-Series Transformations
- Zitierfähige Url:
- https://nbn-resolving.org/urn:nbn:de:bsz:14-qucosa-99211
- Schriftenreihe
- Technische Berichte
- Bandnummer
- 2004,07 (TUD-FI04-07 — May 2004)
- Erstveröffentlichung
- 2004
- ISSN
- 1430-211X
- Abstract (EN)
- In this paper we investigate the relationship between classes of tree-to-tree-series (for short: t-ts) and o-tree-to-tree-series (for short: o-t-ts) transformations computed by restricted deterministic bottom-up weighted tree transducers (for short: deterministic bu-w-tt). Essentially, deterministic bu-w-tt are deterministic bottom-up tree series transducers [EFV02, FV03, ful, FGV04], but the former are de ned over monoids whereas the latter are de ned over semirings and only use the multiplicative monoid thereof. In particular, the common restrictions of non-deletion, linearity, totality, and homomorphism [Eng75] can equivalently be de ned for deterministic bu-w-tt. Using well-known results of classical tree transducer theory (cf., e.g., [Eng75, Fül91]) and also new results on deterministic bu-w-tt, we order classes of t-ts and o-t-ts transformations computed by restricted deterministic bu-w-tt by set inclusion. More precisely, for every commutative monoid we completely specify the inclusion relation of the classes of t-ts and o-t-ts transformations for all sensible combinations of restrictions by means of inclusion diagrams.
- Freie Schlagwörter (EN)
- bottom-up tree-to-tree-series, tree series, tree series transducers
- Klassifikation (DDC)
- 004
- Klassifikation (RVK)
- SS 5514
- Publizierende Institution
- Technische Universität Dresden, Dresden
- URN Qucosa
- urn:nbn:de:bsz:14-qucosa-99211
- Veröffentlichungsdatum Qucosa
- 12.11.2012
- Dokumenttyp
- Forschungsbericht
- Sprache des Dokumentes
- Englisch
- Lizenz / Rechtehinweis