| dc.date.accessioned | 2007-11-26T12:52:38Z | |
| dc.date.available | 2007-11-26T12:52:38Z | |
| dc.date.issued | 2007-11-26T12:52:38Z | |
| dc.identifier.uri | urn:nbn:de:hebis:34-2007112619730 | |
| dc.identifier.uri | http://hdl.handle.net/123456789/2007112619730 | |
| dc.description.sponsorship | F. 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.extent | 236168 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.language.iso | eng | |
| dc.rights | Urheberrechtlich geschützt | |
| dc.rights.uri | https://rightsstatements.org/page/InC/1.0/ | |
| dc.subject | analysis by reduction | eng |
| dc.subject | restarting automaton | eng |
| dc.subject | lexicalization | eng |
| dc.subject | word-expansion | eng |
| dc.subject | degree of nondeterminism | eng |
| dc.subject | context-free language | eng |
| dc.subject.ddc | 004 | |
| dc.title | The Degree of Word-Expansion of Lexicalized RRWW-Automata | eng |
| dc.type | Technischer Report | |
| dcterms.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. | eng |
| dcterms.accessRights | open access | |
| dcterms.alternative | A New Measure for The Degree of Nondeterminism of (Context-Free) Languages | eng |
| dcterms.creator | Mráz, František | |
| dcterms.creator | Plátek, Martin | |
| dcterms.creator | Otto, Friedrich | |
| dcterms.isPartOf | Kasseler Informatikschriften ;; 2007 ,5 | ger |
| 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 | ger |
| dc.subject.ccs | F.1.1 | |
| dc.subject.ccs | F.4.3 | |
| dcterms.source.series | Kasseler Informatikschriften | ger |
| dcterms.source.volume | 2007 ,5 | ger |
