Technischer Report
The Degree of Word-Expansion of Lexicalized RRWW-Automata
(A New Measure for The Degree of Nondeterminism of (Context-Free) Languages)
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.
Förderhinweis
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.Zitieren
@techreport{urn:nbn:de:hebis:34-2007112619730,
author={Mráz, František and Plátek, Martin and Otto, Friedrich},
title={The Degree of Word-Expansion of Lexicalized RRWW-Automata},
year={2007}
}
0500 Oax 0501 Text $btxt$2rdacontent 0502 Computermedien $bc$2rdacarrier 1100 2007$n2007 1500 1/eng 2050 ##0##urn:nbn:de:hebis:34-2007112619730 3000 Mráz, František 3010 Plátek, Martin 3010 Otto, Friedrich 4000 The Degree of Word-Expansion of Lexicalized RRWW-Automata :A New Measure for The Degree of Nondeterminism of (Context-Free) Languages / Mráz, František 4030 4060 Online-Ressource 4085 ##0##=u http://nbn-resolving.de/urn:nbn:de:hebis:34-2007112619730=x R 4204 \$dTechnischer Report 4170 Kasseler Informatikschriften ;; 2007 ,5 7136 ##0##urn:nbn:de:hebis:34-2007112619730
2007-11-26T12:52:38Z 2007-11-26T12:52:38Z 2007-11-26T12:52:38Z urn:nbn:de:hebis:34-2007112619730 http://hdl.handle.net/123456789/2007112619730 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. 236168 bytes application/pdf eng Urheberrechtlich geschützt https://rightsstatements.org/page/InC/1.0/ analysis by reduction restarting automaton lexicalization word-expansion degree of nondeterminism context-free language 004 The Degree of Word-Expansion of Lexicalized RRWW-Automata Technischer Report 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. open access A New Measure for The Degree of Nondeterminism of (Context-Free) Languages Mráz, František Plátek, Martin Otto, Friedrich Kasseler Informatikschriften ;; 2007 ,5 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 F.1.1 F.4.3 Kasseler Informatikschriften 2007 ,5
Die folgenden Lizenzbestimmungen sind mit dieser Ressource verbunden:
:Urheberrechtlich geschützt