Baumrekursionen und Rekursionen mit unregelmäßigem Abstieg

Bomble, Ferdinand Wolfgang; Oberschelp, Walter

doi:HT013433526

Baumrekursionen und Rekursionen mit unregelmäßigem Abstieg

Bomble, Ferdinand Wolfgang (Author)

2002

Verantwortlichkeitsangabevorgelegt von Ferdinand Wolfgang Bomble

ImpressumAachen : Publikationsserver der RWTH Aachen University 2002

UmfangXVI, 259 S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2002

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Oberschelp, Walter (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2002-05-31

Online
URN: urn:nbn:de:hbz:82-opus-3867
URL: https://publications.rwth-aachen.de/record/60331/files/Bomble_Ferdinand.pdf

Einrichtungen

Fakultät für Mathematik, Informatik und Naturwissenschaften (100000)

Inhaltliche Beschreibung (Schlagwörter)
Informatik (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Untypische Rekursionen, die nicht dem Schema der linearen Differenzengleichungen entsprechen, erzeugen Folgen mit ungleichmäßigem Wachstum. Ein gutes Beispiel ist die Heapfolge, die die Anzahl der Heaps mit n Knoten abzählt. Ein wichtiges Ergebnis ist eine neue Darstellung der Heapfolge. Um das Wachstum zu analysieren, wird die Folge der Quotienten betrachtet. Diese Folge zeigt als asymptotische Eigenschaft ein Schwingungsverhalten innerhalb eines Konvergenzkegels. Die Schwingungen erscheinen etwas periodisch und zeigen selbstähnliche Phänomene. Die Analyse von Berührpunkten, Selbstähnlichkeit und anderen Eigenschaften der Quotientenfolge ist eng verknüpft mit unendlichen gelabelten Graphen, speziell binären Bäumen. Die strukturellen Eigenschaften dieser Graphen lösen viele hier untersuchte Probleme. Ein Beispiel einer Eigenschaft, die von Teilgraphen induziert wird, ist die Menge der Berührpunkte. Überabzählbare Berührpunktmengen hängen mit unendlichen Wegen in unendlichen binären Bäumen zusammen. Andererseits führen unendliche Teilbäume und ähnliche Unterstrukturen (nicht notwendigerweise Teilgraphen) zur Selbstähnlichkeit der Quotientenfolge.

Non-regular recursions, which do not satisfy the schema of linear difference equations, define sequences with non-uniform growth. A good example is the heap sequence, which counts the number of heaps with n nodes. An important result is a new representation of the heap sequence. In order to analyse the growth, the sequence of quotients is considered. This sequence shows as asymptotic feature an oscillating behavior inside a convergence cone. The oscillation looks somewhat periodical and shows self-similarity phenomena. The analysis of cluster points, self-similarity etc. of the sequence of quotients is deeply connected with infinite labeled graphs, in particular binary trees. The structural properties of these graphs give answers to many problems which are involved here. An example of a property of the sequence of quotients, which is induced by subgraphs, is the set of cluster points. Uncountable sets of cluster points are connected with infinite paths in infinite binary trees. On the other hand infinite subtrees and similar substructures (not necessarily subgraphs) lead to the self-similarity of the sequence of quotients.

OpenAccess:
PDF
(additional files)