DSpace
KOBRA
KOBRA

KOBRA - Dokumentenserver der Universität Kassel  → Fachbereiche  → FB 10 / Mathematik und Naturwissenschaften  → Institut für Mathematik  → Mathematische Schriften Kassel 

Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:
http://nbn-resolving.de/urn:nbn:de:hebis:34-200604048993

Titel: Restarting automata with restricted utilization of auxiliary symbols
Autor(en): Jurdzinski, TomaszOtto, Friedrich
Klassifikation (DDC): 004 - Informatik (Data processing Computer science)
Erscheinungsdatum: 2005
Herausgeber: Universität Kassel, FB 17, Mathematik/Informatik
Serie/Report Nr.: Mathematische Schriften Kassel05, 02
Zusammenfassung: The restarting automaton is a restricted model of computation that was introduced by Jancar et al. to model the so-called analysis by reduction, which is a technique used in linguistics to analyze sentences of natural languages. The most general models of restarting automata make use of auxiliary symbols in their rewrite operations, although this ability does not directly correspond to any aspect of the analysis by reduction. Here we put restrictions on the way in which restarting automata use auxiliary symbols, and we investigate the influence of these restrictions on their expressive power. In fact, we consider two types of restrictions. First, we consider the number of auxiliary symbols in the tape alphabet of a restarting automaton as a measure of its descriptional complexity. Secondly, we consider the number of occurrences of auxiliary symbols on the tape as a dynamic complexity measure. We establish some lower and upper bounds with respect to these complexity measures concerning the ability of restarting automata to recognize the (deterministic) context-free languages and some of their subclasses.
URI: urn:nbn:de:hebis:34-200604048993
Sammlung(en):Mathematische Schriften Kassel

Dateien zu dieser Ressource:

Datei Beschreibung GrößeFormat
prep0502.pdf250,1 kBAdobe PDFÖffnen/Anzeigen

Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.