Enumeration of Lambda-terms and directed acyclic graphs

Abstract

Enstprechend dem Titel, besteht diese Diplomarbeit aus zwei Teilen. Der erste Teil behandelt Lambda-Terme. Insbesondere sind wir an der Anzahl bestimmter Lambda-Terme einer gewissen Größe interessiert, sowie an der asymptotischen Anzahl, wenn ihre Größe gegen unendlich geht. Wir werden die asymptotische Anzahl an Termen für spezielle Unterklassen von Lambda-Termen herleiten, jedoch nicht für die Klasse aller Lambda-Terme. Dieses Problem ist bisher noch offen und wir werden sehen, dass noch einige Schwierigkeiten bewältigt werden müssen um eine Lösung dafür zu finden. Am Ende des ersten Teils zeigen wir noch einige interessante Eigenschaften über die Struktur von Lambda-Termen. Dabei wird insbesondere auffallen, dass sich diese Struktur grundlegend von der von Bäumen unterscheidet, obwohl Lambda-Terme in enger Beziehung zu Motzkin-Bäumen stehen. Im zweiten Teil dieser Diplomarbeit untersuchen wir sowohl markierte als auch unmarkierte gerichtete azyklische Graphen (directed acyclic graphs, DAGs). Im Fall von markierten DAGs lässt sich das asymptotische Verhalten einfach bestimmen, während das für unmarkierte DAGs noch unbekannt ist. Weiters werden wir einige interessante Resultate über die Struktur von DAGs präsentieren, z.B. dass asymptotisch fast alle DAGs schwach zusammenhängend sind. Zum Schluss werden wir noch zwei Unterklassen von DAGs un- tersuchen, die von besonderem Interesse sind, nämlich sogennante (markierte und unmarkierte) extensionale DAGs und (markierte) essentielle DAGs.

This thesis is divided into two parts. The first part is devoted to the investigation of lambda-terms. Our main goal will be to determine the number of certain lambda-terms of a given size, as well as their asymptotic number as their size tends to infinity. We will derive asymptotic results for various subclasses of lambda-terms, while the problem of counting unrestricted lambda-terms is still unsolved. In order to give an explanation for that, we will explicate the difficulties that have to be overcome in order to be able to establish the asymptotics of lambda-terms. Finally, we will focus on some structural properties of lambda-terms, thereby showing that the structure of lambda-terms highly differs from that of trees, although lambda-terms are closely related to Motzkin-trees. In the second part of this thesis we will investigate both labeled and unlabeled directed acyclic graphs (DAGs). The asympotics for labeled DAGs can be determined easily while the asymptotic behavior of unlabeled DAGs is still unknown. Furthermore we will show some very interesting results on the structure of DAGs, e.g. asymptotically almost all DAGs are weakly connected. At last, we will investigate two subclasses of DAGs that are of special interest, namely (labeled and unlabeled) extensional and (labeled) essential DAGs.