Finite-State Genericity : on the Diagonalization Strength of Finite Automata
type: CreativeWork
description: 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…
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…
author: Busse, Edgar
date published: 2006-04-27
date modified: 2026-07-24T02:30:27Z
provider: Universität Heidelberg
publisher: Networked Digital Library of Theses and Dissertations
type: WebPage
source organization: Universität Heidelberg