Betrachtet man ein Constraint-System derart abstrakt, so stellt sich die Frage, was für systematische Methoden zur Kombination von Constraint-Systemen es gibt. Wichtig ist uns dabei, daß die Methoden allgemeingültig und prinzipieller Natur sind; Spezialverfahren interessieren uns weniger. Eine systematische Methode hat demnach folgendes zu leisten: Einmal muß sie für zwei beliebige Lösungsbereiche ein Verfahren zur Konstruktion eines kombinierten Lösungsbereiches zur Verfügung stellen. Dabei soll der kombinierte Lösungsbereich möglichst allgemeingültig sein, und er sollte wesentliche strukturelle Eigenschaften der Komponentenbereiche mit diesen teilen. Zum zweiten muß die Methode einen Algorithmus beinhalten, der die Lösung von gemischten Constraints über der kombinierten Struktur erlaubt, also die beiden Constraint-Löser der Komponenten zusammenbindet und gemischte Constraints über der vereinigten Constraintsprache in reine Constraints je einer Sprache reduzieren kann, und zwar in solcher Weise, daß es für die reinen Constraints unter Benutzung der Constraint-Löser der jeweiligen Komponenten genau dann eine Lösung gibt, wenn es auch für die gemischten Constraints eine Lösung in der kombinierten Lösungsstruktur gibt. Wir verlangen weiterhin Konservativität in folgendem Sinne: Die Lösung eines reinen Constraints aus einer Komponentensprache soll in der kombinierten Lösungsstruktur zu keinem neuen Resultat führen, ein solcher Constraint soll in der kombinierten Struktur genau dann gelten, wenn er in der Komponentenstruktur gilt.
Wenn man den Begriff von Kombination so allgemein und weit faßt, wie wir es tun, ist es erforderlich, gewisse Einschränkungen bei den Komponentenconstraint-Systemen zu machen. Die erste wichtige Einschränkung betrifft die Signaturen der Komponentenconstraint-Sprachen. Mit Signatur bezeichnet man die Menge der Konstanten, Funktionssymbole und Relationssymbole, aus der die Constraint-Sprache aufgebaut wird. Wir verlangen, daß die Signaturen der Komponentensprachen disjunkt sind, das bedeutet, daß es keine Konstante, kein Funktions- oder Relationssymbol gibt, das in beiden Signaturen auftaucht.
Die zweite wichtige Einschränkung, die wir ziehen, betrifft die Lösungsbereiche. Diese müssen quasi-freie Strukturen sein. Der Begriff der quasi-freien Struktur wurde von F. Baader und K. U. Schulz eingeführt. Er stellt eine Verallgemeinerung des Begriffs der freien Struktur dar und umfaßt viele wichtige nicht-numerische, unendliche Lösungsbereiche. Unter anderem sind Termalgebren, Quotiententermalgebren, rationale Baumalgebren, Vektorräume, erblich endliche fundierte und nicht fundierte Listen, Mengen und Multimengen sowie bestimmte Arten von Feature-Strukturen alle quasi-freie Strukturen. Die wesentliche Erweiterung gegenüber freien Strukturen besteht darin, daß die Elemente des Grundbereiches nicht generiert sein müßen. Es reicht, wenn sie in ihrem Verhalten unter Abbildungen durch das, was mit ihren ``Atomen'' geschieht, determiniert sind. Quasi-freie Strukturen sind symbolisch und unendlich. Dies stellt eine Einschränkung insofern dar, daß numerische Bereiche und endliche Bereiche, die beide wichtige Bereiche für Constraint-Löser darstellen, keine quasi-freien Strukturen sind, und also unsere Methoden der Kombination für diese nicht in Frage kommen.
Baader und Schulz stellen ein erstes allgemeines Kombinationsverfahren vor, das wir eingehend erläutern, da es für unsere Arbeit grundlegend ist. Die kombinierte Lösungsstruktur ist das sogenannte Freie Amalgamierte Produkt. Unter allen sinnvollen kombinierten Strukturen ist es dadurch charakterisiert, die allgemeinste zu sein in dem Sinne, daß ein homomorphes Bild des Freien Amalgamierten Produkts in jeder kombinierten Lösungsstruktur zu finden ist. Die Autoren geben ein allgemeines Verfahren zur Konstruktion des Freien Amalgamierten Produkts für zwei beliebige quasi-freie Strukturen an. Die geforderte Konservativität zeigen sie, indem sie beweisen, daß, betrachtet man jeweils nur eine Komponentensignatur, ``vergißt'' also sozusagen im Freien Amalgamierten Produkt die Signatur der anderen Komponente, das Freie Amalgamierte Produkt und die Komponentenstruktur isomorph sind. Die Autoren präsentieren weiterhin einen Dekompositionsalgorithmus, der gemischte Constraint-Probleme in reine Constraint-Probleme der jeweiligen Komponenten zerlegt. Mit Hilfe dieses Dekompositionsalgorithmus beweisen sie, daß die positive Theorie des Freien Amalgamierten Produktes entscheidbar ist, wenn die positiven Theorien der Komponentenstrukturen entscheidbar sind.
Der erste Teil unseres Beitrags setzt sich mit diesem Dekompositionsalgorithmus auseinander und gibt Optimierungsverfahren an. Der Dekompositionsalgorithmus beinhaltet drei nichtdeterministische Schritte, die einen so großen Suchraum aufspannen, daß sich eine Implementation dieses Algorithmus schlicht verbietet. Um also den Dekompositionsalgorithmus auch für Anwendungen brauchbar zu machen, muß man Optimierungsverfahren finden, die den Suchraum drastisch einschränken. Dabei lag unser Interesse darin, möglichst allgemeine Verfahren zu finden, die auf fast alle Constraint-Löser von quasi-freien Strukturen anwendbar sind. Es werden zwei solch allgemeiner Optimierungsverfahren vorgestellt, genannt die deduktive und die iterative Methode. Die iterative Methode wurde für den Fall entwickelt, da eine größere Zahl von Komponenten als nur zwei kombiniert werden. Sie beruht auf der Beobachtung, daß das Dekompositionsverfahren in so einem Fall den Suchraum stark vergrößert, da alle möglichen nicht-deterministischen Entscheidungen getroffen werden, bevor auch nur eine Komponente zu lösen versucht wird. Im Gegensatz dazu arbeitet die iterative Methode lokal. Sie legt die nicht-deterministischen Entscheidungen jeweils nur für eine Komponente fest, und schreitet erst dann zur nächsten fort, wenn ein Satz von Entscheidungen getroffen wurde, für den der Komponentenconstraint-Löser eine Lösung findet. Die Aufgabe bei dieser an sich einfachen Idee besteht darin, zu zeigen, daß das so modifizierte Verfahren unsere Anforderung noch erfüllt, daß es dann und nur dann eine Lösung für ein gemischtes Constraint-Problem im Freien Amalgamierten Produkt gibt, wenn es Lösungen für reine Constraint-Probleme in den Komponenten gibt.
Die deduktive Methode beruht auf der Einsicht, daß nicht alle Entscheidungen im Dekompositionsalgorithmus nicht-deterministisch getroffen werden müssen. Oft stellen das zu lösende Constraint-Problem und die einzelnen Komponenten Vorgaben, wie eine bestimmte Entscheidung zu treffen ist, soll das Problem noch lösbar sein. Man benötigt dazu neue Constraint-Löser für die Komponenten, die am Prozeß der Suche nach den richtigen Entscheidungen beteiligt werden können. Diese müssen für ein ihnen vorgelegtes reines Constraint-Problem dann nicht mehr nur Lösbarkeit feststellen, sondern auch angeben können, welche Entscheidungen im Algorithmus wie zu treffen sind, damit ihr reines Constraint-Problem lösbar bleibt. Der Kombinationsalgorithmus wird bei der deduktiven Methode damit zu einer Art Moderator. Er befragt reihum die beteiligten Komponentenlöser, welche Entscheidungen wie zu treffen sind. Wenn schließlich die Komponentenlöser keine weiteren Entscheidungen festlegen können, trifft der Kombinationsalgorithmus eine nichtdeterministische Entscheidung und beginnt die Konsultation der Komponentenlöser erneut, bis schließlich auf diesem Wege alle Entscheidungen getroffen sind. Sagen dann noch alle Komponentenlöser, daß ihre reinen Constraintprobleme lösbar sind, so ist auch das ursprüngliche gemischte Problem lösbar.
Da die beiden Optimierungsverfahren völlig unabhängig voneinander sind, lassen sie sich in eines integrieren. Die Verfahren sind tatsächlich implementiert, um ihren Effekt auch testen zu können. Von uns durchgeführte Tests zeigen, daß viele Constraint-Probleme mit den Optimierungen um Größenordnungen schneller gelöst werden können, und einige Probleme erst mit dem optimierten Verfahren praktisch lösbar sind.
Der zweite Beitrag behandelt die sogenannte Rationale Amalgamierung. Dabei handelt es sich um eine zweite allgemeine Kombinationsmethode neben dem Freien Amalgamierten Produkt. Obwohl das Freie Amalgamierte Produkt eine allgemeinste kombinierte Lösungsstruktur darstellt, gibt es doch in der Praxis Kombinationen, die nicht Instanzen des Freien Amalgamierten Produktes sind. Beispiele dafür sind Arbeiten von A. Colmerauer über die Kombination von rationalen Bäumen und rationalen Listen, sowie Arbeiten von W. Rounds und A. Moshier und C. Pollard über die Kombination von Feature-Strukturen und nicht-fundierten Mengen. In allen diesen Fällen sind die Komponentenstrukturen ``rational''. Freie Amalgamierung ist daher nicht die Kombination der Wahl für diese Constraint-Systeme, da die Elemente in der kombinierten Lösungsstruktur nicht rational, sondern endlich sind, das heißt, gemischte Constraints, in denen ein unendlich häufiger Wechsel von der einen Komponente in die andere verlangt wird, sind im Freien Amalgamierten Produkt nicht lösbar.
Dies ist der Ansatzpunkt der Rationalen Amalgamierung. Sie stellt eine kombinierte Lösungsstruktur bereit, in der rationale Elemente vorhanden, mithin solche Constraints lösbar sind. Damit ist Rationale Amalgamierung die Methode der Wahl bei der Kombination von rationalen Komponentenstrukturen. Sie liefert ein allgemeines Konstruktionsverfahren für eine rationale kombinierte Lösungsstruktur, gegeben zwei beliebige sogenannte nicht-kollabierende quasi-freie Strukturen. Auch für diese kombinierte Lösungsstruktur läßt sich zeigen, daß bei Einschränkung auf jeweils eine Signatur nur einer Komponente die kombinierte Struktur isomorph ist zur Komponentenstruktur. Damit ist die Forderung nach Konservativität erfüllt. Wir beweisen, daß das Freie Amalgamierte Produkt bis auf Isomorphie eine Teilstruktur der Rationalen Amalgamierung ist. Auch das folgende Theorem zeigt die Natürlichkeit der Konstruktion: Die rationale Amalgamierung zweier rationaler Baumalgebren über disjunkten Signaturen ist isomorph zur rationalen Baumalgebra über der vereinigten Signatur. Der Dekompositionsalgorithmus für Rationale Amalgamierung ist eine vereinfachte Variante des Algorithmus für das Freie Amalgamierte Produkt; der letzte der drei nichtdeterministischen Schritte ist bei Rationaler Amalgamierung nicht erforderlich. Mithilfe dieses Dekompositionsalgorithmus läßt sich zeigen, daß die Lösbarkeit von gemischten Constraints in der Rationalen Amalgamierung entscheidbar ist, wenn die Lösbarkeit reiner Constraints (mit gewissen technischen Zusatzbedingungen) in den Komponentenstrukturen entscheidbar ist. Damit ist ein zweites allgemeines Kombinationsverfahren gegeben.
Der dritte Beitrag befaßt sich mit Negation bei der Kombination von Constraint-Systemen. Die Constraints, die in den bisherigen Teilen betrachtet wurden, waren allesamt positive Constraints, enthielten also weder Negation noch Implikation. Nun ist aber insbesondere die Implikation ein sprachliches Mittel, auf das man bei der Formulierung von Constraint-Problemen ungern verzichtet. Sie wird beispielsweise verwendet, um Constraint-Entailment auszudrücken, das bei der Reduktion von Constraintmengen wichtig ist. In einem ersten Teil setzen wir uns daher mit der Kombination von Constraint-Systemen, deren Sprachen Negation enthalten, auseinander. Dabei gehen wir vom Freien Amalgamierten Produkt als kombinierter Lösungsstruktur aus und verwenden als Algorithmus eine Erweiterung des Dekompositionsalgorithmus um die Behandlung negativer Formeln, aber ohne neue nichtdeterministische Schritte. Wir zeigen, daß das existenzielle Fragment der vereinigten Signatur, also Konjunktionen und Disjunktionen von gemischten Atomformeln und gemischten negierten Atomformeln, im Freien Amalgamierten Produkt entscheidbar ist, wenn die existenziellen Fragmente der Komponenten mit gewissen technischen Zusatzbedingungen entscheidbar sind. Weiterhin geben wir Bedingungen für die Lösungen in den Komponenten an, unter denen sich im Freien Amalgamierten Produkt Grundlösungen für gemischte Constraint-Probleme finden lassen, da bei Constraint-Problemen mit Negation oftmals ein besonderes Interesse an Grundlösungen besteht. Leider kann man aus Arbeiten von R. Treinen erkennen, daß sich im allgemeinen im Freien Amalgamierten Produkt auch dann kein größeres Quantorenfragment als das existenzielle entscheiden läßt, wenn dies in den Komponenten möglich ist. Es ergibt sich außerdem, daß Rationale Amalgamierung für die Kombination von Constraint-Systemen mit Negation höchstens in Spezialfällen geeignet ist, allgemein jedoch nicht.
Im zweiten Teil dieses Beitrags geht es um die sogenannte Unabhängigkeitseigenschaft negativer Constraints. Ein Constraint-System besitzt die Unabhängigkeitseigenschaft, wenn für jede Konjunktion von positiven Constraints und jede Konjunktion von negativen Constraints gilt: Die beiden Konjunktionen sind zusammen lösbar genau dann, wenn für jeden negativen Constraint die Konjunktion positiver Constraints zusammen mit dem negativen Constraint lösbar ist. Man kann also die negativen Constraints unabhängig voneinander lösen. Diese Eigenschaft ist wichtig in praktischen Constraint-Lösern. Sie ermöglicht es, einen Constraint-Löser nur für positive Constraints zu entwickeln und mit diesem dennoch mithilfe einer übersetzung auch negative Constraints zu lösen. Zuerst einmal ohne Berücksichtigung von Kombinationen untersuchen wir, welche quasi-freien Strukturen die Unabhängigkeitseigenschaft besitzen, wobei wir einen besonderen Blick auf Gleichungstheorien werfen, da diese eine wichtige Rolle unter den quasi-freien Strukturen spielen. Für Gleichungstheorien ergibt sich, daß unitäre Theorien die Unabhängigkeitseigenschaft besitzen, finitäre aber nicht. Es gibt Theorien vom Typ 0, die die Unabhängigkeitseigenschaft besitzen. Für die Kombination von Gleichungstheorien erhält man folgendes Modularitätsresultat: Das Freie Amalgamierte Produkt zweier unitärer, regulärer und kollaps-freier Theorien ist wieder unitär, hat mithin also die Unabhängigkeitseigenschaft. Blickt man nun allgemeiner auf quasi-freie Strukturen, so sieht man, daß auch hier die unitären Strukturen die Unabhängigkeitseigenschaft besitzen. Und es gibt infinitäre Strukturen mit Unabhängigkeitseigenschaft. Zum Abschluß läßt sich auch das Modularitätsresultat verallgemeinern. Das Freie Amalgamierte Produkt zweier unitärer, regulärer und nicht kollabierender quasi-freier Strukturen ist wieder unitär, hat somit die Unabhängigkeitseigenschaft.