DSpace
KOBRA
KOBRA

KOBRA - Dokumentenserver der Universität Kassel  → Fachbereiche  → FB 16 Elektrotechnik / Informatik  → Kasseler Informatikschriften (KIS)  

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

Titel: The Degree of Word-Expansion of Lexicalized RRWW-Automata
Sonstige Titel: A New Measure for The Degree of Nondeterminism of (Context-Free) Languages
Autor(en): Mráz, FrantišekPlátek, MartinOtto, Friedrich
Klassifikation (DDC): 004 - Informatik (Data processing Computer science)
Erscheinungsdatum: 26-Nov-2007
Serie/Report Nr.: Kasseler Informatikschriften2007 ,5
Zusammenfassung: Restarting automata can be seen as analytical variants of classical automata as well as of regulated rewriting systems. We study a measure for the degree of nondeterminism of (context-free) languages in terms of deterministic restarting automata that are (strongly) lexicalized. This measure is based on the number of auxiliary symbols (categories) used for recognizing a language as the projection of its characteristic language onto its input alphabet. This type of recognition is typical for analysis by reduction, a method used in linguistics for the creation and verification of formal descriptions of natural languages. Our main results establish a hierarchy of classes of context-free languages and two hierarchies of classes of non-context-free languages that are based on the expansion factor of a language.
URI: urn:nbn:de:hebis:34-2007112619730
Bemerkungen: Einige der Ergebnisse dieser Arbeit wurden auf der CIAA 2007 in Prag (Juli 2007) vorgestellt. Der entsprechende Beitrag mit dem Titel "A measure for the degree of nondeterminism of context-free languages" steht auf den Seiten 192-202 im Tagungsband dieser Konferenz. Titel des Tagungsbandes: "Implementation and Application of Automata", 12th International Conference, CIAA 2007, Prague, Czech Republic, July 16-18, 2007, Revised Selected Papers. Serie: "Lecture Notes in Computer Science". Erschienen am 24.10.07 im Springer Verlag Berlin. ISBN 978-3-54-76335-2
Sammlung(en):Kasseler Informatikschriften (KIS)

Dateien zu dieser Ressource:

Datei Beschreibung GrößeFormat
Technicalreport2007_5.pdf234,66 kBAdobe PDFÖffnen/Anzeigen

Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.