Algorithmic Aspects of Ordered Structures

In dieser Arbeit verbinden wir die Theorie der Quasi-Ordnungen mit der Theorie der Algorithmen einiger kombinatorischer Objekte. Zuerst entwickeln wir die Theorie der Wohl-Quasi-Ordnungen, WQO, im Zusammenhang zur maximalen Komplexität. Dann geben wir ein allgemeines 0-1-Gesetz für erbliche Eigenschaften, das Auswirkungen für die mittlere Komplexität hat. Dieses Ergebnis für mittlere Komplexität wird auf die Klasse der endlichen Graphen, versehen mit der Relation ``induzierter Subgraph'', angewendet. Wir erhalten, daß eine große Klasse von Problemen, welche z.B. Perfektheit umfaßt, Algorithmen mit im Mittel konstanter Laufzeit haben. Dann zeigen wir, indem wir ein Ergebnis von Damaschke für Cographen veralgemeinern, daß die Klassen der endlichen Ordnungen bzw. Graphen mit beschränktem Dekompositionsdurchmesser bzgl. der Relation ``induzierte Subordnung'' bzw. ``induzierter Subgraph'' WQO sind. Dies führt uns zu linearen Erkennungsalgorithmen für alle erblichen Eigenschaften über diesen Objekten. Unser Hauptresultat ist dann, daß die Menge der endlichen partiellen Ordnungen eine Wohl-Quasi-Ordnung bzgl. einer gewissen Relation ≤ , der sogenannten Ketten-Minor-Relation, ist. Um dies zu beweisen, führen wir eine verwandte Relation auf endlichen formalen Sprachen ein, die die gleiche Eigenschaft hat. Als Folgerung erhalten wir, daß jede Eigenschaft, die erblich bzgl. ≤ ist, einen Test in O(|P|c) Zeit zuläßt, wobei $c$ von der Eigenschaft abhängt. Dieser Test läßt sich leicht parallelisieren. Auf einer parallelen Maschine (\CRCW\ \PRAM) kann er so implementiert werden, daß er konstante Zeit auf O(|P|c) Prozessoren benötigt.In this work we relate the theory of quasi-orders to the theory of algorithms over some combinatorial objects. First we develope the theory of well-quasi-orderings, wqo's, and relate it to the theory of worst-case complexity. Then we give a general 0-1-law for hereditary properties that has implications for average-case complexity. This result on average-case complexity is applied to the class of finite graphs equipped with the induced subgraph relation. We obtain that a wide class of problems, including e.g. perfectness, has average constant time algorithms. Then we show, by extending a result of Damaschke on cographs, that the classes of finite orders resp. graphs with bounded decomposition diameter form wqo's with respect to the induced suborder resp. induced subgraph relation. This leads to linear time algorithms for the recognition of any hereditary property on these objects. Our main result is then that the set of finite posets is a wqo with respect to a certain relation ≤, called chain minor relation. To prove this we introduce a similar relation on finite formal languages that also has this property. As a consequence we obtain that every property which is hereditary with respect to ≤ has a test in O(|P|c) whereas c depends on the property. This test has an easy parallelization with the same costs. On a parallel machine (CRCW PRAM) it may be implemented in such a way that it runs in constant time and needs O(|P|c) processors