Alternation as a programming paradigm

Abstract

In der Komplexitätstheorie versteht man unter alternierenden Maschinen, nichtdeterministische Maschinen bei denen existentielle und universelle Zustände alternieren. Unter einer nichtdeterministischen Maschine versteht man eine Maschine bei der es in jedem Zustand mehrere Möglichkeiten für die weitere Berechnung geben kann. Existentielle Zustände akzeptieren die Eingabe dann wenn mindestens eine der möglichen Berechnungen die Eingabe akzeptiert. Universelle Zustände akzeptieren die Eingabe nur dann wenn alle möglichen Berechnungen die Eingabe akzeptieren.<br />Die Komplexitätsklassen die mittels alternierenden Maschinen definiert werden stehen in einem starken Zusammenhang mit der Hierarchie der gewöhnlichen deterministischen Komplexitätsklassen. Deshalb werden alternierende Algorithmen oft verwendet um zu zeigen das Probleme in bestimmten Komplexitätsklassen lösbar sind. Alternierende Algorithmen sind also ein nützliches Werkzeug in der Komplexitätstheorie, dennoch gibt es keine Programmiersprache die dieses Konzept für die Praxis bereitstellt. Das Paradebeispiel für Problem mit einem alternierenden Kern sind Spiele. Die Frage die uns bei Spielen interessiert ist ob es eine Gewinnstrategie für den Startspieler gibt. Um diese Frage zu beantworten müssen wir rekursiv folgendes Problem lösen. Existiert ein Zug für den Startspieler sodass für alle möglichen Züge des Gegners es wieder eine Gewinnstrategie für den Startspieler gibt. Viele bekannte Spiele, wie zum Beispiel Go, sind in der Komplexitätstheorie als inhärent schwierige Probleme bekannt und damit auch für praktische Programmierung uninteressant. Es gibt aber eine weite Bandbreite von Spielen und anderen alternierenden Problem mit niedriger Komplexität die auch in der Praxis berechnet werden können. Alternierung scheint also ein nützliches Programmier Paradigma in der Theorie zu sein, es stellt sich also die Frage ob es sich auch in einer praktischen Programmiersprache umsetzen lässt. Um es in der Praxis auch nutzen zu können stellt sich weiter die Frage nach einer Umgebung in der sich die alternierenden Programme auch effizient ausführen lassen.<br />In dieser Arbeit identifizieren wir zunächst natürliche alternierende Probleme die mit akzeptablem Aufwand berechenbar sind. Das sind Probleme die sehr komplizierte deterministische Algorithmen benötigen aber mit dem Konzept der Alternierung sehr intuitiv gelöst werden können.<br />Dann führen wir eine Sprache ein die es ermöglicht in einer kompakten und intuitiven Art alternierende Programme zu schreiben. Wir untermauern die Natürlichkeit dieser Sprache mit einer Reihe von Programmbeispielen für die vorher identifizierten Probleme.<br />Weiters stellen wir ein System vor, das diese alternierenden Programme auf eine effiziente Art simuliert.<br />

In computational complexity theory alternating machines are nondeterministic machines which alternate between existential and universal states. A nondeterministic machine in each computation state may have several possibilities for the further computation. An existential state accepts an input if at least one of this possible computations leads to acceptance. An universal state accepts an input only if all possible computations lead to acceptance. There is a strong connection between the complexity classes defined by alternating machines and deterministic complexity classes. So the concept of alternating algorithms is often used in computational complexity theory to show that a problem is decidable in a specific complexity class. Alternating algorithms are useful to solve problems in theory but there is no language to use this concept for practical programming. Very natural examples of problems with an alternating character are games, more precisely, the question if there is a winning strategy for the start player in the game. To find a winning strategy we recursively look for a move for the start player such that for all possible moves of the opponent he has a winning strategy. Many popular games, for example Go, are known to be inherent hard problems for computational purposes, so that they can't be solved in practice. But there is also a large class of games that can be computed in reasonable time.<br />What is missing is a framework that allows us to apply this useful theoretic alternating constructs in practical programming. Further it should simulate the alternating programs in a feasible way to make alternating programming practicable.<br />In this thesis we first identify natural alternating problems which are feasible computable. So these are problems which induce very complex deterministic algorithms but can be intuitively solved with an alternating algorithm. Then we break down the theoretic model of alternating machines to an intuitive language for writing alternating programs in practice. We confirm the intuitiveness of our language by presenting some alternating programs. Further we introduce a framework that simulates these alternating programs in an efficient way.