Reguläre Häufigkeitsberechnungen

Abstract

Die vorliegende Arbeit beschäftigt sich mit Häufigkeitsberechnungen, einem rekursionstheoretischen Begriff, der in den 60er Jahren von Rose eingeführt wurde. Eine Funktion f ist berechenbar mit Frequenz m/n, wenn es einen Algorithmus gibt, der für je n verschiedene Eingaben n Ausgabewerte berechnet, von denen mindestens m mit den zugehörigen Funktionswerten von f übereinstimmen. Eine erste natürliche Fragestellung war: gibt es nicht-berechenbare Funktionen, die mit einer Frequenz nahe 1 berechnet werden können? Trakhtenbrot beantwortete diese Frage 1963 negativ, indem er zeigte, dass eine Funktion mit Frequenz echt größer als 1/2 bereits berechenbar im herkömmlichen Sinne ist. Andererseits gibt es überabzählbar viele Funktionen, die sich mit Frequenz 1/2 berechnen lassen. Also ist dieses Ergebnis optimal. Die Forschung auf diesem Gebiet intensivierte sich daraufhin: Wissenschaftler wie Dëgtev, Kinber und Trakhtenbrot selbst (in den 70er und 80er Jahren) und Beigel, Gasarch, Hinrichs, Kummer, Stephan, Tantau und Wechsung (ab den 90er Jahren) beschäftigten sich mit verschiedenen Aspekten von Häufigkeitsberechnungen und verwandten Berechenbarkeitsbegriffen. In der vorliegenden Arbeit beschäftigen wir uns vorwiegend mit regulären Häufigkeitsberechnungen, also solchen, die von endlichen Automaten vorgenommen werden können. Kinber untersuchte diesen Aspekt als erster im Jahre 1976 und behauptete, dass sich Trakhtenbrots Resultat auf endliche Automaten überträgt. Sein folgerte dies aus einem allgemeineren Resultats über separierbare Sprachen, das sich allerdings als falsch herausstellte (ein Gegenbeispiel wurde 2002 von Tantau angegeben). (Zwei disjunkte Sprachen A und B heißen separierbar, wenn ein Algorithmus alle Wörter aus A akzeptiert und alle Wörter aus B ablehnt). Die Frage, ob das Analogon von Trakhtenbrots Resultat für endliche Automaten gilt, stellte sich also von neuem. Diese Dissertation enthält folgende Ergebnisse. In Kapitel 2 geben wir zwei Beweise für Trakhtenbrots Resultat an. Zunächst präsentieren wir seinen Originalbeweis, um dann einen neuen kombinatorischen Beweis zu geben, der einen großen Vorteil besitzt: er erlaubt die Übertragung des Ergebnisses auf endliche Automaten. Zwei kleinere Resultate beschließen dieses Kapitel: der Nachweis, dass es überabzählbar viele nicht häufigkeitsberechenbare Sprachen gibt, und eine Darstellung des Zusammenhangs von Häufigkeitsberechnungen und sog. mulit-selektiven Mengen. In Kapitel 3 arbeiten wir den Fehler in Kinbers Beweis über separierbare Sprachen heraus und geben ein konkretes Gegenbeispiel an. Dann untersuchen wir die Separierbarkeit von sog. Pfad- und Anti-Pfadsprachen, die wie folgt definiert sind: sei alpha ein unendliches Wort über dem Alphabet { 0, 1 }; dann ist A(alpha) die Menge der endlichen Präfixe von alpha, und B(alpha) die Menge der Wörter von A(alpha), bei denen das letzte Bit negiert wurde. Wir zeigen, dass A(alpha) und B(alpha) genau dann separiert werden können, wenn die 1-Positionen von alpha berechnet werden können. Andererseits gibt es überabzählbar viele alpha, für die A(alpha) und B(alpha) mit Frequenz 1/2 berechnet werden können. Wenn (ab drei Eingaben) nur ein Fehler zugelassen ist, dann sind A(alpha) und B(alpha) bereits rekursiv. Dieses Ergebnis überträgt sich auch auf endliche Automaten. Zum Abschluss dieses Kapitels zeigen wir, dass sich Kinbers Vermutung (dass Trakhtenbrots Resultat auch für Sprachen gilt, die durch endliche Automaten separiert werden können) nicht retten lässt: für jede Konstante q < 1 gibt es Werte 1 <= m < n mit m/n > q und ein alpha derart, dass A(alpha) und B(alpha) durch endliche Automaten mit Frequenz m/n separiert werden können, jedoch nicht rekursiv separierbar sind. In Kapitel 4 untersuchen wir verschiedene Aspekte regulärer Häufigkeitsberechnungen. Wir zeigen zunächst, dass sich Trakhtenbrots Resultat auf endliche Automaten überträgt, indem wir den neuen Beweis aus Kapitel 2 nochmals genauer betrachten. Anschließend zeigen wir, dass aperiodische Automaten, die Häufigkeitsberechnungen durchführen, nur aperiodische reguläre Sprachen berechnen können (aperiodische Sprachen entsprechen sternfreien Sprachen). Dann beweisen wir ein sog. Iterationskriterium, das vergleichbar mit dem bekannten Pumping-Lemma für reguläre Sprachen ist und uns für viele konkrete Beispielsprachen den Nachweis erlaubt, dass diese nicht häufigkeitsberechenbar sind. Im letzten Teil untersuchen wir dann Abschlusseigenschaften der Klasse der regulär häufigkeitsberechenbaren Sprachen: wir zeigen, dass sie eine boolesche Algebra bilden, jedoch nicht unter Spiegelung abgeschlossen sind. Darüberhinaus ist die Vereinigung zweier Sprachen, die mit Frequenz 1/n erkennbar sind, in der Regel nicht 1/n-erkennbar. Wir beweisen eine untere Schranke, die sehr nah an der besten bekannten oberen Schranke liegt.

This thesis deals with frequency computations, a recursion theoretic notion that was introduced by Rose in 1960. A function f is said to be computable with frequency m/n, if there is an algorithm that, for every n distinct input values, computes n output values, and at least m of these values coincide with the corresponding values of the function f. A first question arose naturally: are there non-computable functions that are computable with a frequency close to 1? Trakhtenbrot answered this questions negatively in 1963 by showing that a function computable with frequency strictly greater than 1/2 is already computable in the usual sense. On the other hand, there are uncountably many functions computable with frequency 1/2, thus this result is optimal. Research in this area intensified after Trakhtenbrot's result, with persons like Dëgtev, Kinber and Trakhtenbrot himself during the 70s and early 80s, and Beigel, Gasarch, Hinrichs, Kummer, Stephan, Tantau, Wechsung and others from the 90s onwards, working on different aspects of frequency computations and related notions. In this work we mostly deal with regular frequency computations, which are frequency computations performed by finite automata. Kinber was the first to investigate this direction in 1976, and claimed that Trakhtenbrot's result carries over to finite automata. He proved this as a corollary of a more general result concerning the separation of languages via finite automata, which turned out to be wrong (a counterexample was given by Tantau in 2002). (Two disjoint languages A and B are seperable if an algorithm accepts all words from A and rejects all words from B.) Thus, the question whether the analogon of Trakhtenbrot's result holds for finite automata posed itself once more. In this thesis, we prove the following results. In Chapter 2 we give two proofs of Trakhtenbrot's theorem. First, we present a self-contained version of his original proof, and second, we give a new combinatorial proof which has one major advantage over Trakhtenbrot's: it allows the transfer of this result to finite automata. Two minor results end this chapter: the existence of uncountably many non-frequency computable languages, and a connection between frequency computations and so-called multi-selective languages. In Chapter 3 we work out the error in Kinber's proof about seperable languages, and give a concrete counterexample. Afterwards, we investigate the separation of so-called path and anti-path languages, which are defined as follows: let alpha be an infinite word over the alphabet { 0, 1 }; then A(alpha) is the set of finite prefixes of alpha, and B(alpha) is the set of words from A(alpha) with the last bit toggled. We show that A(alpha) and B(alpha) are seperable if and only if the positions of alpha containing a 1 are computable. On the other hand, there are uncountably many alpha for which A(alpha) and B(alpha) are seperable with frequency 1/2. If it is possible to seperate A(alpha) and B(alpha) with one error (given at least three inputs), then these languages are already recursive. This result carries over to finite automata as well. We end this chapter by showing that Kinber's claim, a Trakhtenbrot-like result for the seperation of languages by finite automata, fails badly: for any constant q < 1 there are values 1 <= m < n with m/n > q and an alpha such that A(alpha) and B(alpha) can be seperated by finite automata with frequency m/n, but are not recursively seperable. In Chapter 4 we investigate different aspects of regular frequency computations. First we show that Trakhtenbrot's result for general frequency computations carries over to finite automata, by a close inspection of the new proof given in Chapter 2. We then show that aperiodic automata can--in the frequency computation sense - only compute aperiodic regular languages (the class of aperiodic languages is equivalent to the class of star-free languages). Next we prove a so-called iteration criterion, which is comparable to the well-known pumping lemma for regular languages, and allows us to show for many concrete example languages that they are not frequency computable. Then, in the last part, we investigate closure properties of the class of languages frequency computable by finite automata: we show that they form a Boolean algebra, but are not closed under the reversal operation. Furthermore, the union of two languages which are computable with frequency 1/n is, in general, not computable with frequency 1/n. We give a lower bound which is very close to the best-known upper bound.