• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

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.

Page generated in 0.1382 seconds