Return to search

Inclusion Diagrams for Classes of Deterministic Bottom-up Tree-to-Tree-Series Transformations

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.

Identiferoai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:26217
Date12 November 2012
CreatorsMaletti, Andreas
PublisherTechnische Universität Dresden
Source SetsHochschulschriftenserver (HSSS) der SLUB Dresden
LanguageEnglish
Detected LanguageEnglish
Typedoc-type:workingPaper, info:eu-repo/semantics/workingPaper, doc-type:Text
Rightsinfo:eu-repo/semantics/openAccess
Relationurn:nbn:de:bsz:14-qucosa-79344, qucosa:24841

Page generated in 0.0016 seconds