Loading…
On structural similarities of finite automata and Turing machine enumerability classes
Tantau, Till
Die Komplexität von Funktionen, die Worte auf Worte abbilden, kann auf verschiedene Arten gemessen werden. Bekannte Maße sind Zeit- und Platzkomplexität. Aufzählbarkeit ist ein weiteres Komplexitätsmaß. Sie wird in der Rekursionstheorie eingesetzt, wo sie eine zentrale Rolle in der Theorie fragenbeschränkter Reduktionen spielt, sowie in der ressourcebeschränkten Komplexitätstheorie, insbesondere in Verbindung mit nichtuniformen Berechnungen. In dieser Arbeit wird das Konzept der Aufzählbarkeit auf endliche Automaten übertragen. Es wird gezeigt, dass sich Aufzählbarkeit in der Rekursionstheorie und in der Automatentheorie gleichartig verhält, in der Komplexitätstheorie hingegen andersartig. Die Aufzählbarkeit einer Funktion f ist die kleinste Zahl m, für die ein m-Aufzähler für f existiert. Ein m-Aufzähler ist eine Maschine, die bei Eingabe eines Wortes w eine Menge von höchstens m Möglichkeiten für f(w) ausgibt. Verschiedene Klassen können durch Veränderung des Parameters m und der Art der erlaubten Maschinen definiert werden. In der Rekursionstheorie erlaubt man beliebige Turingmaschinen als Aufzähler, in der Automatentheorie lediglich endliche Automaten. Ein tief liegendes strukturelles Resultat, das sowohl für Turingmaschinen als auch für endliche Automaten gilt, ist der folgende Kreuzproduktsatz: Ist f × g eine (n + m)-aufzählbare Funktion, so ist entweder f eine n-aufzählbare oder g eine m-aufzählbare Funktion. Dieser Satz gilt nicht im Polynomialzeitfall. Aufzählbarkeit kann auch benutzt werden, um die Komplexität von Sprachen zu quantifizieren. Dazu wird gefragt, wie schwierig es ist, die n-fache charakteristische Funktion chiAn und die n-fache Kardinalitätsfunktion #An einer Sprache A aufzuzählen. Eine Sprache A ist (m, n)-verbose, falls chiAn m-aufzählbar ist. Die Inklusionsstrukturen der Verbosenessklassen von Turingmaschinen und der von endlichen Automaten sind gleich: alle (m, n)-Turing-verbosen Sprachen sind genau dann auch (h, k)-Turing-verbose, wenn alle in Bezug auf endliche Automaten (m, n)-verbosen Sprachen auch (h, k)-verbose sind. Dies gilt nicht im Polynomialzeitfall. Die Aufzählbarkeit von #An ist in der Rekursionstheorie wohluntersucht. Kummers Kardinalitätssatz besagt, dass A rekursiv ist, falls #An von einer Turingmaschine n-aufzählbar ist. Vermutlich gilt dieser Satz auch für endliche Automaten: zumindest der Nonspeedupsatz, der Kardinalitätssatz für zwei Worte und der eingeschränkte Kardinalitätssatz gelten für endliche Automaten. Der Kardinalitätssatz gilt nicht im Polynomialzeitfall. Die Hauptbeweise in dieser Arbeit benutzen zwei Techniken, deren Einsatz auch in anderen Gebieten vielversprechend erscheint: generische Beweise und Astdiagonalisierung. Generische Beweise benutzen elementare Definitionen, ein Konzept aus der Logik, um Aufzähler zu definieren. Solche Beweise lassen sich auf alle Berechnungsmodelle anwenden, die unter elementaren Definitionen abgeschlossen sind. Dies ist für endliche Automaten der Fall, aber auch für die Presburger-Arithmetik und die Ordinalzahlarithmetik. Die zweite Technik ist eine neue Diagonalisierungsmethode, bei der Maschinen auf dem Kode der bisherigen Folge von Diagonalisierungsentscheidungen ausgetrickst werden und nicht auf ihrem eigenen Kode. Astdiagonalisierung ist nicht universell einsetzbar, aber wo sie eingesetzt werden kann, kann man mit ihrer Hilfe gegen Turingmaschinen mittels endlicher Automaten diagonalisieren. Die Resultate über Aufzählbarkeitsklassen haben auch in anderen Gebieten Anwendungen, so bei Protokolltests mittels endlicher Automaten, bei Klassifikationsproblemen mit Beispielen und bei Trennbarkeitsfragen. Ein schönes Beispiel einer solchen Anwendung lautet wie folgt: Existieren regulär Obermengen von A × A, A × ar A, und ar A × ar A, deren Schnitt leer ist, so ist A regulär. Gedruckte Version im Wissenschaft und Technik Verlag, Berlin [http://www.wt-verlag.de] erschienen.
There are different ways of measuring the complexity of functions that map words to words. Well-known measures are time and space complexity. Enumerability is another possible measure. It is used in recursion theory, where it plays a key role in bounded query theory, but also in resource-bounded complexity theory, especially in connection with nonuniform computations. This dissertation transfers enumerability to automata theory. It is shown that enumerability behaves similarly in recursion theory and in automata theory, but differently in complexity theory. The enumerability of a function f is the smallest m such that there exists an m-enumerator for f. An m-enumerator is a machine that produces, for every input word w, a set of up to m possibilities for f(w). By varying the parameter m and the class of allowed enumerators, different enumerability classes can be defined. In recursion theory, one allows arbitrary Turing machines as enumerators; in automata theory, only finite automata. A deep structural result that holds both for finite automata and for Turing machine enumerability is the following cross product theorem: if f × g is (n + m)-enumerable, then either f is n-enumerable or g is m-enumerable. In contrast, this theorem does not hold for polynomial-time enumerability. Enumerability can be used to quantify the difficulty of a language A by asking how difficult it is to enumerate its n-fold characteristic function chiAn and cardinality function #An. A language is (n, m)-verbose if chiAn is m-enumerable. The inclusion structures of Turing machine and of finite automata verboseness classes are identical: all (n, m)-Turing-verbose languages are (h, k)-Turing-verbose iff all (n, m)-fa-verbose languages are (h, k)-fa-verbose. The structure of polynomial-time verboseness classes is different. The enumerability of #An has been studied in detail in recursion theory. Kummer's cardinality theorem states that if #An is n-enumerable by a Turing machine, then A must be recursive. Evidence is gathered that this theorem also holds for finite automata: it is shown that the nonspeedup theorem, the cardinality theorem for two words, and the restricted cardinality theorem all hold for finite automata. The cardinality theorem does not hold for polynomial-time computations. The central proofs rely on two proof techniques that promise to be applicable in other situations as well: generic proofs and branch diagonalisation. Generic proofs use elementary definitions, a concept from logic, to define enumerators in terms of other enumerators. They can be instantiated for all computational models that are closed under elementary definitions. Examples of such models are finite automata, but also Presburger arithmetic and ordinal number arithmetic. The second technique is a new diagonalisation method, where machines are tricked on codes of diagonalisation decision sequences, rather than on codes of machines. Branch diagonalisation is not applicable universally, but where it is applicable, it can be used to diagonalise against Turing machines, using only finite automata. Results on enumerability classes have applications in unrelated areas, like finite automata protocol testing, classification problems where examples are provided, and separability. An intriguing example of such an application is the following theorem: if there exist regular supersets of A × A, A × ar A, and ar A × ar A whose intersection is empty, then A is regular. Printed version available from Wissenschaft und Technik Verlag, Berlin [http://www.wt-verlag.de]
