Andreas Maletti

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

Dokumente und Dateien

Hinweis

Bitte nutzen Sie beim Zitieren immer folgende Url:

http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-99211

Kurzfassung in Englisch

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.

weitere Metadaten

Erschienen in Technische Berichte
Titel der Schriftenreihe
(Deutsch)
Technische Berichte / Technische Universität Dresden, Fakultät Informatik ; 2004,07 (TUD-FI04-07 — May 2004)
Schlagwörter
(Englisch)
bottom-up tree-to-tree-series, tree series, tree series transducers
DDC Klassifikation004
RVK KlassifikationSS 5514
Institution(en) 
HochschuleTechnische Universität Dresden
FakultätFakultät Informatik
DokumententypForschungsbericht
SpracheEnglisch
Erstveröffentlichungjahr der Druckausgabe2004
Veröffentlichungsdatum (online)12.11.2012
persistente URNurn:nbn:de:bsz:14-qucosa-99211
ISSN1430-211X

Hinweis zum Urheberrecht

Diese Website ist eine Installation von Qucosa - Quality Content of Saxony!
Sächsische Landesbibliothek Staats- und Universitätsbibliothek Dresden