TY  - THES
A3  - Alsmeyer, Gerold
A3  - Alsmeyer, G.
AB  - Die Arbeit behandelt die Verwendung von Markov-Erneuerungstheorie in der Analyse von zufälligen Strings und verwandten Baumstrukturen, sowie iterierten Funktionensystemen. Die Modelle beinhalten Markov-Modulation durch eine positiv rekurrente diskrete Markov-Kette. Teil I untersucht Baumstrukturen, insbesondere Tries, die in der Analyse von Algorithmen auftreten und aus zufälligen Strings konstruiert werden. Ein String wird von einer Markov Source erzeugt, bildet also eine Markov-Kette und gleichzeitig die Steuerkette eines Markov-modulierten Hilfsprozesses. Wir bestimmen in der ersten Hälfte das Grenzverhalten charakteristischer Parameter wie Tiefe und Imbalance Factor, und entwickeln in der zweiten Hälfte ein Resultat für die Average-Case Analyse weiterer charakteristischer Parameter. Teil II untersucht iterierte Funktionensystem aus Markov-modulierten Lipschitz-stetigen Funktionen. Wir betten unser Modell ein in das stationäre Regime von Elton, und geben Bedingungen für polynomielle und geometrische Konvergenz.
AU  - Godland, Philipp
DA  - 2020
KW  - Markov-Erneuerungstheorie
KW  - Markov Random Walk
KW  - Regenerative Methoden
KW  - Tries
KW  - Analyse von Algorithmen
KW  - Iterierte Funktionensysteme
LA  - eng
N1  - Münster (Westfalen), Univ., Diss., 2020
PY  - 2020
TI  - Markov renewal theory in the analysis of random strings and iterated function systems
UR  - https://nbn-resolving.org/urn:nbn:de:hbz:6-70179618340
Y2  - 2024-12-27T10:45:36
ER  -