Global ETD Search

1	Inclusion Diagrams for Classes of Deterministic Bottom-up Tree-to-Tree-Series Transformations Maletti, Andreas 12 November 2012 (has links) (PDF) 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. bottom-up tree-to-tree-series tree series tree series transducers ddc:004 rvk:SS 5514
2	Inclusion Diagrams for Classes of Deterministic Bottom-up Tree-to-Tree-Series Transformations Maletti, Andreas 12 November 2012 (has links) 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. info:eu-repo/classification/ddc/004 ddc:004
3	Composition of Tree Series Transformations Maletti, Andreas 12 November 2012 (has links) (PDF) Tree series transformations computed by bottom-up and top-down tree series transducers are called bottom-up and top-down tree series transformations, respectively. (Functional) compositions of such transformations are investigated. It turns out that the class of bottomup tree series transformations over a commutative and complete semiring is closed under left-composition with linear bottom-up tree series transformations and right-composition with boolean deterministic bottom-up tree series transformations. Moreover, it is shown that the class of top-down tree series transformations over a commutative and complete semiring is closed under right-composition with linear, nondeleting top-down tree series transformations. Finally, the composition of a boolean, deterministic, total top-down tree series transformation with a linear top-down tree series transformation is shown to be a top-down tree series transformation. tree series transformation weighted tree automata tree series transducers top-down tree series bottom-up tree series ddc:004 rvk:SS 5514
4	Composition of Tree Series Transformations Maletti, Andreas 12 November 2012 (has links) Tree series transformations computed by bottom-up and top-down tree series transducers are called bottom-up and top-down tree series transformations, respectively. (Functional) compositions of such transformations are investigated. It turns out that the class of bottomup tree series transformations over a commutative and complete semiring is closed under left-composition with linear bottom-up tree series transformations and right-composition with boolean deterministic bottom-up tree series transformations. Moreover, it is shown that the class of top-down tree series transformations over a commutative and complete semiring is closed under right-composition with linear, nondeleting top-down tree series transformations. Finally, the composition of a boolean, deterministic, total top-down tree series transformation with a linear top-down tree series transformation is shown to be a top-down tree series transformation. info:eu-repo/classification/ddc/004 ddc:004
5	Pure and O-Substitution Maletti, Andreas 12 November 2012 (has links) (PDF) The basic properties of distributivity and deletion of pure and o-substitution are investigated. The obtained results are applied to show preservation of recognizability in a number of surprising cases. It is proved that linear and recognizable tree series are closed under o-substitution provided that the underlying semiring is commutative, continuous, and additively idempotent. It is known that, in general, pure substitution does not preserve recognizability (not even for linear target tree series), but it is shown that recognizable linear probability distributions (represented as tree series) are closed under pure substitution. o-substitution pure substitution tree series substitution distributivity ddc:004 rvk:SS 5514
6	Charakterisierung erkennbarer Baumreihen über starken Bimonoiden durch gewichtete MSO-Logik Märcker, Steffen 20 October 2017 (has links) Endliche Wortautomaten ermöglichen es, reguläre Wortsprachen sowohl zu erkennen als auch zu erzeugen. Julius Richard Büchi gelang es, diese erkennbaren Wortsprachen mithilfe der monadischen Logik zweiter Stufe, kurz MSO, zu charakterisieren [7, 19]. Dieses Ergebnis wurde dann auf erkennbare Baumsprachen, das heißt Mengen von geordneten Bäumen, die durch einenAufwärtsbaumautomaten erkannt werden, erweitert [11, 28]. Anstelle der <-Relation auf den Positionen eines Wortes tritt dabei die Kindrelation edgei(x; y) für die Positionen eines Baumes. Die erkennbaren Wort- und Baumsprachen haben breite Anwendung in der Informatik gefunden. Zu den bekanntesten gehören beispielsweise reguläre Ausdrücke und Syntaxbäume vieler Programmiersprachen. Im Zusammenspiel mit XML ist die Schemasprache RelaxNG zur Dokumentvalidierung [9, 29], im Gegensatz zu XML-Schema, durch die reiche Theorie erkennbarer Baumsprachen fundiert. info:eu-repo/classification/ddc/000 ddc:000
7	Pure and O-Substitution Maletti, Andreas 12 November 2012 (has links) The basic properties of distributivity and deletion of pure and o-substitution are investigated. The obtained results are applied to show preservation of recognizability in a number of surprising cases. It is proved that linear and recognizable tree series are closed under o-substitution provided that the underlying semiring is commutative, continuous, and additively idempotent. It is known that, in general, pure substitution does not preserve recognizability (not even for linear target tree series), but it is shown that recognizable linear probability distributions (represented as tree series) are closed under pure substitution. info:eu-repo/classification/ddc/004 ddc:004
8	Contributions to the theory and applications of tree languages Högberg, Johanna January 2007 (has links) This thesis is concerned with theoretical as well as practical aspects of tree languages. It consists of an introduction and eight papers, organised into three parts. The ﬁrst part is devoted to algorithmic learning of regular tree languages, the second part to bisimulation minimisation of tree automata, and the third part to tree-based generation of music. We now summarise the contributions made in each part. In Part I, an inference algorithm for regular tree languages is presented. The algorithm is a generalisation of a previous algorithm by Angluin, and the learning task is to derive, with the aid of a so-called MAT-oracle, the minimal (partial and deterministic) ﬁnite tree automaton M that recognises the target language U over some ranked alphabet Σ. The algorithm executes in time O(\|Q\| \|δ\| (m + \|Q\|)), where Q and δ are the set of states and the transition table of M , respectively, r is the maximal rank of any symbol in Σ, and m is the maximum size of any answer given by the oracle. This improves on a similar algorithm by Sakakibara as dead states are avoided both in the learning phase and in the resulting automaton. Part I also describes a concrete implementation which includes two extensions of the basic algorithm. In Part II, bisimulation minimisation of nondeterministic weighted tree automata (henceforth, wta) is introduced in general, and for ﬁnite tree automata (which can be seen as wta over the Boolean semiring) in particular. The concepts of backward and forward bisimulation are extended to wta, and eﬃcient minimisation algorithms are developed for both types of bisimulation. In the special case where the underlying semiring of the input automaton is either cancellative or Boolean, these minimisation algorithms can be further optimised by adapting existing partition reﬁnement algorithms by Hopcroft, Paige, and Tarjan. The implemented minimisation algorithms are demonstrated on a typical task in natural language processing. In Part III, we consider how tree-based generation can be applied to algorithmic composition. An algebra is presented whose operations act on musical pieces, and a system capable of generating simple musical pieces is implemented in the software Treebag: starting from input which is either generated by a regular tree grammar or provided by the user via a digital keyboard, a number of top-down tree transducers are applied to generate a tree over the operations provided by the music algebra. The evaluation of this tree yields the musical piece generated. regular tree languages tree series algorithmic learning MAT-learning bisimulation minimisation tree-based generation algorithmic composition music algebra Computer science Datalogi
9	Kleene-Type Results for Weighted Tree-Automata / Kleeneartige Resultate für Gewichtete Baumautomaten Pech, Christian 08 March 2004 (has links) (PDF) The main result of this thesis is the generalization of the Kleene-theorem to formal tree-series over commutative semirings (the Kleene theorem states the coincidence between rational and recognizable formal languages). To this end weighted tree-languages are introduced and the Kleene-theorem is proved for them. The desired result for formal tree-series is then obtained through application of a homomorphism that relates weighted tree-languages with formal tree-series. In the second part of the thesis the connections to the theorie of Iteration-theories are discovered. In particular it is shown there that the grove-theory of formal tree-series forms a partial iteration-theory. / Hauptresultat dieser Arbeit ist die Verallgemeinerung des Satzes von Kleene über die Koinzidenz der rationalen und der erkennbaren Sprachen auf den Fall der formalen Baumreihen über kommutativen Semiringen. Zu diesem Zweck werden gewichtete Baumsprachen eingeführt, da sich diese ählich den klassischen Baumsprachen verhalten. Der Satz von Kleene wird also zunächst auf den Fall der gewichteten Baumsprachen verallgemeinert. Das erstrebte Resultat wird dann durch Anwendung eines Homomorphismus', der gewichteten Baumsprachen formle Baumreihen zuordnet, erhalten. Im zweiten Teil der Arbeit werden Kreuzverbindungen zur Theorie der Iterationstheorien aufgezeigt. Insbesondere wird z.B. gezeigt, dass die Grovetheorie der formalen Baumreihen eine partielle Iterationstheorie bildet. Automat Baum Baumautomat Baumreihe Fixpunkt Gewicht Iterationstheorie Kleene Kosten Schützenberger Sprache gewichtet rational regulär Kleene Schützenberger automaton cost fixedpoint iteration-theory language rational regular tree tree-series weight weighted ddc:510 rvk:SK 130 Automat Baum &lt;Mathematik&gt; Baumautomat Fixpunkt Formale Sprache Iterationstheorie
10	Kleene-Type Results for Weighted Tree-Automata Pech, Christian 18 August 2003 (has links) The main result of this thesis is the generalization of the Kleene-theorem to formal tree-series over commutative semirings (the Kleene theorem states the coincidence between rational and recognizable formal languages). To this end weighted tree-languages are introduced and the Kleene-theorem is proved for them. The desired result for formal tree-series is then obtained through application of a homomorphism that relates weighted tree-languages with formal tree-series. In the second part of the thesis the connections to the theorie of Iteration-theories are discovered. In particular it is shown there that the grove-theory of formal tree-series forms a partial iteration-theory. / Hauptresultat dieser Arbeit ist die Verallgemeinerung des Satzes von Kleene über die Koinzidenz der rationalen und der erkennbaren Sprachen auf den Fall der formalen Baumreihen über kommutativen Semiringen. Zu diesem Zweck werden gewichtete Baumsprachen eingeführt, da sich diese ählich den klassischen Baumsprachen verhalten. Der Satz von Kleene wird also zunächst auf den Fall der gewichteten Baumsprachen verallgemeinert. Das erstrebte Resultat wird dann durch Anwendung eines Homomorphismus', der gewichteten Baumsprachen formle Baumreihen zuordnet, erhalten. Im zweiten Teil der Arbeit werden Kreuzverbindungen zur Theorie der Iterationstheorien aufgezeigt. Insbesondere wird z.B. gezeigt, dass die Grovetheorie der formalen Baumreihen eine partielle Iterationstheorie bildet. info:eu-repo/classification/ddc/510 ddc:510

Search results