The Degree of Word-Expansion of Lexicalized RRWW-Automata

Simple item page
dc.date.accessioned2007-11-26T12:52:38Z
dc.date.available2007-11-26T12:52:38Z
dc.date.issued2007-11-26T12:52:38Z
dc.description.everythingEinige 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-2ger
dc.description.sponsorshipF. Mráz and M.Plátek were supported by the program 'Information Society' under project 1ET100300517. F. Mráz was also supported by the Grant Agency of Charles University in Prague under Grant-No. 358/2006/A-INF/MFF.eng
dc.format.extent236168 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.uriurn:nbn:de:hebis:34-2007112619730
dc.identifier.urihttp://hdl.handle.net/123456789/2007112619730
dc.language.isoeng
dc.rightsUrheberrechtlich geschützt
dc.rights.urihttps://rightsstatements.org/page/InC/1.0/
dc.subjectanalysis by reductioneng
dc.subjectrestarting automatoneng
dc.subjectlexicalizationeng
dc.subjectword-expansioneng
dc.subjectdegree of nondeterminismeng
dc.subjectcontext-free languageeng
dc.subject.ccsF.1.1
dc.subject.ccsF.4.3
dc.subject.ddc004
dc.titleThe Degree of Word-Expansion of Lexicalized RRWW-Automataeng
dc.typeTechnischer Report
dcterms.abstractRestarting 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.eng
dcterms.accessRightsopen access
dcterms.alternativeA New Measure for The Degree of Nondeterminism of (Context-Free) Languageseng
dcterms.creatorMráz, František
dcterms.creatorPlátek, Martin
dcterms.creatorOtto, Friedrich
dcterms.isPartOfKasseler Informatikschriften ;; 2007 ,5ger
dcterms.source.seriesKasseler Informatikschriftenger
dcterms.source.volume2007 ,5ger

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
Technicalreport2007_5.pdf
Size:
234.66 KB
Format:
Adobe Portable Document Format
Download

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
2.33 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

Kasseler Informatikschriften (KIS)