eprintid: 6392
rev_number: 8
eprint_status: archive
userid: 1
dir: disk0/00/00/63/92
datestamp: 2006-05-03 12:51:05
lastmod: 2014-04-03 19:40:08
status_changed: 2012-08-14 15:18:13
type: doctoralThesis
metadata_visibility: show
creators_name: Busse, Edgar
title: Finite-State Genericity : on the Diagonalization Strength of Finite Automata
title_de: Finite-State Generizität : die Diagonalisierungsstärke endlicher Automaten
ispublished: pub
subjects: ddc-510
divisions: i-110400
adv_faculty: af-11
keywords: Formale Sprachen , saturierte Folge , Bi-immunität , Moore-Funktion , Diagonalisierungsstärkecomputability , finite-state Genericity , bi-immunity , diagonalization
cterms_swd: Generizität
cterms_swd: Ressourcenbeschränkte Generizität
cterms_swd: Komplexitätstheorie
cterms_swd: Berechenbarkeit
cterms_swd: Berechnungskomplexität
cterms_swd: Automat
cterms_swd: Automat <Automatentheorie
abstract: Algorithmische Generizit¨atskonzepte spielen eine wichtige Rolle in der Berechenbarkeitsund Komplexit¨atstheorie. Diese Begriffe stehen in engem Zusammenhang mit grundlegenden Diagonalisierungstechniken, und sie wurden zur Erzielung starker Trennungen von Komplexit¨atsklassen verwendet. Da f¨ur jedes Generizit¨atskonzept die zugeh¨origen generischen Mengen eine co-magere Klasse bilden, ist die Analyse generischer Mengen ein wichtiges Hifsmittel f¨ur eine quantitative Analyse struktureller Ph¨anomene. Typischerweise werden Generizit¨atskonzepte mit Hilfe von Erweiterungsfunktionen definiert, wobei die St¨arke eines Konzepts von der Komplexit¨at der zugelassenen Erwiterungsfunktionen abh¨angt. Hierbei erweisen sich die sog. schwachen Generizit¨atskonzepte, bei denen nur totale Erweiterungsfunktionen ber¨ucksichtigt werden, meist als wesentlich schw¨acher als die vergleichbaren allgemeinen Konzepte, bei denen auch partielle Funktionen zugelassen sind. Weiter sind die sog. beschr¨ankten Generizit¨atskonzepte – basierend auf Erweiterungen konstanter L¨ange – besonders interessant, da hier die Klassen der zugeh¨origen generischen Mengen nicht nur co-mager sind sondern zus¨atzlich Maß 1 haben. Generische Mengen diesen Typs sind daher typisch sowohl im topologischen wie im maßtheoretischen Sinn. In dieser Dissertation initiieren wir die Untersuchung von Generizit¨at im Bereich der Theorie der Formalen Sprachen: Wir f¨uhren finite-state-Generizit¨atskonzepte ein und verwenden diese, um die Diagonalisierungsst¨arke endlicher Automaten zu erforschen. Wir konzentrieren uns hierbei auf die beschr¨ankte finite-state-Generizit¨at und Spezialf ¨alle hiervon, die wir durch die Beschr¨ankung auf totale Erweiterungsfunktionen bzw. auf Erweiterungen konstanter L¨ange erhalten. Wir geben eine rein kombinatorische Charakterisierung der beschr¨ankt finite-state-generischen Mengen: Diese sind gerade die Mengen, deren charakteristische Folge saturiert ist, d.h. jedes Bin¨arwort als Teilwort enth¨alt. Mit Hilfe dieser Charakterisierung bestimmen wir die Komplexit¨at der beschr¨ankt finitestate- generischen Mengen und zeigen, dass solch eine generische Menge nicht regul¨ar sein kann es aber kontext-freie Sprachen mit dieser Generizit¨atseigenschaft gibt. Die von uns betrachteten unbeschr¨ankten finite-state-Generizit¨atskonzepte basieren auf Moore-Funktionen und auf Verallgemeinerungen dieser Funktionen. Auch hier vergleichen wir die St¨arke der verschiedenen korrespondierenden Generizit¨atskonzepte und er¨ortern die Frage, inwieweit diese Konzepte m¨achtiger als die beschr¨ankte finite-state-Generizit ¨at sind. Unsere Untersuchungen der finite-state-Generizit¨at beruhen zum Teil auf neuen Ergebnissen ¨uber Bi-Immunit¨at in der Chomsky-Hierarchie, einer neuen Chomsky-Hierarchie f¨ur unendliche Folgen und einer gr¨undlichen Untersuchung der saturierten Folgen. Diese Ergebnisse – die von unabh¨angigem Interesse sind – werden im ersten Teil der Dissertation vorgestellt. Sie k¨onnen unabh¨angig von dem Hauptteil der Arbeit gelesen werden.
abstract_translated_text: Algorithmic genericity notions play a major role in computability theory and computational 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 phenomena. 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 functions, where in general weak genericity notions based only on total extension functions are much weaker than the corresponding genericity notions allowing partial extension functions too. Moreover, so called bounded genericity concepts based on extensions of constant 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 language 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 characterization of bounded finite-state genericity by showing that a set A is bounded finite-state generic if and only if its characteristic sequence is saturated, i.e., contains any binary string as a subword. 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.
abstract_translated_lang: eng
date: 2006
date_type: published
id_scheme: DOI
id_number: 10.11588/heidok.00006392
ppn_swb: 513921508
own_urn: urn:nbn:de:bsz:16-opus-63923
date_accepted: 2006-04-27
advisor: HASH(0x55fc36d4e410)
language: eng
bibsort: BUSSEEDGARFINITESTAT2006
full_text_status: public
citation:   Busse, Edgar  (2006) Finite-State Genericity : on the Diagonalization Strength of Finite Automata.  [Dissertation]     
document_url: https://archiv.ub.uni-heidelberg.de/volltextserver/6392/1/BusseProm.pdf