Finite-state genericity [Elektronische Ressource] : on the diagonalization strength of finite automata / vorgelegt von Edgar Busse (geb. Damir Serikovich Muldagaliev)

Sujets

• Informatik
• Mathematics

Informations

• Publié par: ruprecht-karls-universitat_heidelberg
• Publié le: 01 janvier 2006
• Nombre de lectures: 17
• Langue: Deutsch

Extrait

INAUGURAL DISSERTATION
zur
Erlangung der Doktorwurde¨
der
¨Naturwissenschaftlich Mathematischen Gesamtfakultat
der
Ruprecht Karls Universit at¨
Heidelberg
vorgelegt von
Diplom Mathematiker Edgar Busse
( geb. Damir Serikovich Muldagaliev )
aus Almaty
Tag der mundlichen¨ Prufung:¨ 27. April 2006Thema
Finite State Genericity
On the Diagonalization Strength of Finite
Automata
Gutachter: Prof. Dr. Klaus Ambos Spies
Prof. Dr. Frank StephanZusammenfassung
Algorithmische Generizitatsk¨ onzepte spielen eine wichtige Rolle in der Berechenbarkeits
und Komplexitatstheorie.¨ Diese Begriffe stehen in engem Zusammenhang mit grundle
genden Diagonalisierungstechniken, und sie wurden zur Erzielung starker Trennungen von
Komplexitatsklassen¨ verwendet. Da fur¨ jedes Generizitatsk¨ onzept die zugehorigen¨ gener-
ischen Mengen eine co magere Klasse bilden, ist die Analyse generischer Mengen ein
wichtiges Hifsmittel fur¨ eine quantitative Analyse struktureller Phanomene.¨ Typischer-
weise werden Generizitatsk¨ onzepte mit Hilfe von Erweiterungsfunktionen definiert, wobei
die Stark¨ e eines Konzepts von der Komplexitat¨ der zugelassenen Erwiterungsfunktionen
abhangt.¨ Hierbei erweisen sich die sog. schwachen Generizitatsk¨ onzepte, bei denen nur
totale Erweiterungsfunktionen berucksichtigt¨ werden, meist als wesentlich schwacher¨ als
die vergleichbaren allgemeinen Konzepte, bei denen auch partielle Funktionen zugelassen
sind. Weiter sind die sog. beschrankten¨ Generizitatsk¨ onzepte – basierend auf Erweiterun
gen konstanter Lange¨ – besonders interessant, da hier die Klassen der zugehorigen¨ gener-
ischen Mengen nicht nur co mager sind sondern zusatzlich¨ Maß 1 haben. Generische
Mengen diesen Typs sind daher typisch sowohl im topologischen wie im maßtheoretis
chen Sinn.
In dieser Dissertation initiieren wir die Untersuchung von Generizitat¨ im Bereich der
Theorie der Formalen Sprachen: Wir fuhren¨ finite state Generizit atsk¨ onzepte ein und ver-
wenden diese, um die Diagonalisierungsstark¨ e endlicher Automaten zu erforschen.
Wir konzentrieren uns hierbei auf die beschrankte¨ finite state Generizit at¨ und Spezial
falle¨ hiervon, die wir durch die Beschrankung¨ auf totale Erweiterungsfunktionen bzw. auf
Erweiterungen konstanter Lange¨ erhalten. Wir geben eine rein kombinatorische Charak
terisierung der beschrankt¨ finite state generischen Mengen: Diese sind gerade die Men
gen, deren charakteristische Folge saturiert ist, d.h. jedes Binarw¨ ort als Teilwort enthalt.¨
Mit Hilfe dieser Charakterisierung bestimmen wir die Komplexitat¨ der beschrankt¨ finite
state generischen Mengen und zeigen, dass solch eine generische Menge nicht regular¨ sein
kann es aber kontext freie Sprachen mit dieser Generizitatseigenschaft¨ gibt. Weiter un
tersuchen wir den Einfluss der Lange¨ der Erweiterungen und der Beschrankung¨ auf totale
Erweiterungsfunktionen auf die Stark¨ e der korrespondierenden Generizitatsk¨ onzepte. Die
Untersuchung von eingeschrankten¨ Erweiterungsfunktionen, deren Wert jeweils nur von
¨ ¨ ¨ ¨der Eingabenlange oder einem Endstuck der Eingabe konstanter Lange abhangt, verdeut
licht weiter die geringe Diagonalisierungsstark¨ e endlicher Automaten. Wir beenden un
sere Untersuchung der beschrankten¨ finite state Generizit at¨ damit, dass wir zeigen, dass
die Stark¨ e dieser Konzepte dramatisch erhoht¨ wird, wenn wir Erweiterungsfunktionen zu
grundelegen, deren Eingaben Anfangstuck¨ e in redundanter Darstellung sind. Auf diese
Art erhalten wir beschrankt¨ finite state generische Mengen, die REG bi immun sind, d.h.
deren Erkennung die Kapazitat¨ eines endlichen Automaten nicht nur unendlich oft sondern
fast uberall¨ uberschreitet.¨
Die von uns betrachteten unbeschrankten¨ finite state Generizit atsk¨ onzepte basieren
auf Moore Funktionen und auf Verallgemeinerungen dieser Funktionen. Auch hier verglei
chen wir die Stark¨ e der verschiedenen korrespondierenden Generizitatsk¨ onzepte und eror ¨
tern die Frage, inwieweit diese Konzepte machtiger¨ als die beschrankte¨ finite state Generi
zitat¨ sind.Unsere Untersuchungen der finite state Generizit at¨ beruhen zum Teil auf neuen Ergeb
nissen uber¨ Bi Immunitat¨ in der Chomsky Hierarchie, einer neuen Chomsky Hierarchie
¨ ¨fur unendliche Folgen und einer grundlichen Untersuchung der saturierten Folgen. Diese
Ergebnisse – die von unabhangigem¨ Interesse sind – werden im ersten Teil der Dissertation
vorgestellt. Sie konnen¨ unabhangig¨ von dem Hauptteil der Arbeit gelesen werden.Abstract
Algorithmic genericity notions play a major role in computability theory and computa
tional complexity theory. These notions are closely related to important diagonalization
techniques and they can be used for obtaining strong separations of complexity classes.
Moreover, since for any genericity concept, the class of the correspondent generic sets is
comeager, the analysis of generic sets leads to a quantitative analysis of structural phenom
ena. Typically, genericity concepts are based on partial or total extension functions, where
the strength of a concept is determined by the complexity of the admissible extension func
tions, where in general weak genericity notions based only on total extension functions are
much weaker than the corresponding genericity notions allowing partial extension func
tions too. Moreover, so called bounded genericity concepts based on extensions of con
stant length are of particular interest since the classes of the corresponding generic sets are
not only comeager but also have measure 1. So generic sets of these types are abundant in
the topological and the measure theoretic sense.
In this thesis we initiate the investigation of genericity in the setting of formal lan
guage theory: We introduce finite state genericity notions, i.e., genericity notions related
to the lowest class in the Chomsky hierarchy and we apply these concepts to explore the
diagonalization strength of finite automata.
We focus on bounded finite state genericity and some special cases hereof allowing
only total extensions and extensions of fixed length. We give a purely combinatorial char-
acterization of bounded finite state genericity by showing that a setA is bounded finite state
generic if and only if its characteristic sequence is saturated, i.e., contains any binary string
as a subword. We use this characterization for determining the complexity of bounded
finite state generic sets. In particular we show that no bounded finite state generic lan
guage is regular but that there are such languages which are context free. Moreover, we
explore the impact of the length of the admissible extensions and of the question whether
we allow partial or only total extension functions. We further illustrate the limitations
of the diagonalization strength of finite automata by considering some restricted types of
extension strategies, namely length invariant and oblivious extensions. We complete our
investigation of bounded finite state genericity by showing that the strength of these con
cepts can be dramatically increased if we work with more redundant representations of
initial segments: This way we obtain bounded finite state generic sets which are REG bi
immune, i.e., sets which exceed the capacity of finite automata not only infinitely often but
almost everywhere.
The unbounded finite state genericity concepts which we consider are based on Moore
functions and various generalizations of these functions. Again we compare the strength
of different concepts and discuss the question in which respect these concepts are more
powerful than bounded finite state genericity.
Our analysis of finite state genericity is based in part on new results on bi immunity
in the Chomsky hierarchy, on a Chomsky hierarchy of sequences, and a thorrough analysis
of saturated sequences. These results – which are of independent interest – are presented
in the first part of the thesis and can be read independently.Contents
1 Introduction 1
2 Formal Languages and Infinite Sequences 11
2.1 Notation and Basic Concepts . . . . . . . . . . . . . . . . . . . . 13
2.2 Grammars and Automata . . . . . . . . . . . . . . . . . . . . . . 15
2.2.1 Chomsky Grammars and the Chomsky Hierarchy . . . . . 15
2.2.2 Regular Languages and Finite Automata . . . . . . . . . . 18
2.2.3 Context Free Languages and Push Down Automata . . . . 21
2.2.4 Turing Machines and Complexity . . . . . . . . . . . . . 23
2.3 Regular Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.4 Strong Separations in the Chomsky Hierarchy . . . . . . . . . . . 37
2.4.1 Bi Immunity and Almost Everywhere Complexity . . . . 38
2.4.2 Definitions and Basic Facts . . . . . . . . . . . . . . . . . 39
2.4.3 Immunity to the Class of Regular Languages . . . . . . . 42
2.4.4 to the Classes of Linear and Context Free Lan
guages . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.4.5 Immunity to the Higher Classes of the Chomsky Hierarchy 44
2.4.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . .