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

Please use this identifier to cite or link to this item: http://nbn-resolving.de/urn:nbn:de:hebis:34-2007112619730

Title: The Degree of Word-Expansion of Lexicalized RRWW-Automata
Other Titles: A New Measure for The Degree of Nondeterminism of (Context-Free) Languages
Authors: Mráz, FrantišekPlátek, MartinOtto, Friedrich
???metadata.dc.subject.ddc???: 004 - Informatik (Data processing Computer science)
Issue Date: 26-Nov-2007
Series/Report no.: Kasseler Informatikschriften2007 ,5
Abstract: 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
???metadata.dc.description.everything???: 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
Appears in Collections:Kasseler Informatikschriften (KIS)

Files in This Item:

File Description SizeFormat
Technicalreport2007_5.pdf234.66 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.