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.
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:26217 |
| Date | 12 November 2012 |
| Creators | Maletti, Andreas |
| Publisher | Technische Universität Dresden |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | English |
| Detected Language | English |
| Type | doc-type:workingPaper, info:eu-repo/semantics/workingPaper, doc-type:Text |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | urn:nbn:de:bsz:14-qucosa-79344, qucosa:24841 |
Page generated in 0.1836 seconds