Diese Arbeit gibt einen Überblick über die kombinatorischen Aspekte von monoton wachsend markierten Strukturen mit einem Schwerpunkt auf Modellen aus der Informatik. Die Hauptobjekte dieser Untersuchung sind wachsende Bäume, Bucket-wachsende Bäume, wachsende Schaltkreise sowie drei verschiedene Modelle konkurrierender Prozesse. Die bestehende Literatur zu diesen Themen bildet die Grundlage dieser Masterarbeit. Die wesentlichen verwendeten Werkzeuge sind die Methode der Singularitätenanalyse sowie Grenzverteilungsresultate für eine Verallgemeinerung von Pólya–Eggenberger-Urnenmodellen. Für wachsende Bäume umfassen die Ergebnisse exakte und asymptotische Abzählresultate, ein asymptotisches multivariates Normalitätsgesetz für die Verteilung der Knotengrade in sehr einfachen Familien wachsender Bäume sowie eine Untersuchung der Höhe rekursiver Bäume. Die Abzählresultate werden auf Bucket-wachsende Bäume verallgemeinert. Es wird ein Phasenübergangssatz über die multivariate Grenzverteilung der Bucket-Kapazitäten für einige Familien von Bucket-wachsenden Bäumen angegeben, der das zuvor bekannte Resultat über Bucket-rekursive Bäume verallgemeinert, indem ein neues Monotonieergebnis verwendet wird. Für wachsende Schaltkreise wird eine asymptotische Normalität der Anzahl der Ausgabeknoten gezeigt, und die Tiefe zufälliger rekursiver Schaltkreise wird untersucht. Abschließend werden asymptotische Abzählresultate für wachsende Diamanten, wachsende „fork–join“ Prozesse und wachsende Bogenprozesse angegeben. Einige dieser Ergebnisse werden anschließend verwendet, um Abschätzungen für die durchschnittliche Anzahl zulässiger Ausführungen solcher Prozesse zu erhalten.
de
This thesis gives an overview of the combinatorial aspects of increasingly labeled structures with a focus on models from computer science. The main objects of study are increasing trees, bucket increasing trees, increasing circuits, and three different models of concurrent processes. The existing literature on these topics provides the foundation of this thesis. The main tools used are the method of singularity analysis and distributional limit results for a generalization of Pólya–Eggenberger urn models. For increasing trees, results include exact and asymptotic enumeration results, an asymptotic joint normality law for the degree counts in so-called very simple families of increasing trees, and a study of the height of recursive trees. The enumeration results are then generalized to bucket increasing trees. A phase transition theorem about the joint limiting distribution of the bucket capacities for some families of bucket increasing trees is given, generalizing the previously known result about bucket recursive trees by employing a new monotonicity result. For increasing circuits, an asymptotic normality of the number of output nodes is shown, and the depth of random recursive circuits is studied. Lastly, asymptotic enumeration results for increasing diamonds,increasing fork–join processes, and increasing arch processes are given. Some of these results are then used in order to obtain estimates for the average number of admissible executions of such processes.
en
Additional information:
Arbeit an der Bibliothek noch nicht eingelangt - Daten nicht geprüft
