. "Pl\u00E1tek, Martin" . "000269304000011" . . "309306" . . "The degree of word-expansion of lexicalized RRWW-automata - A new measure for the degree of nondeterminism of (context-free) languages"@en . "RIV/00216208:11320/09:00206906!RIV10-MSM-11320___" . "FR - Francouzsk\u00E1 republika" . . . . . "37" . "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 occurrences 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."@en . . . "Theoretical Computer Science" . "[E8515F9807B8]" . "The degree of word-expansion of lexicalized RRWW-automata - A new measure for the degree of nondeterminism of (context-free) languages" . . "P(1ET100300517), Z(MSM0021620838)" . . "9"^^ . "degree; word-expansion; lexicalized; RRWW-automata; measure; degree; nondeterminism; context-free; languages"@en . "11320" . . "Mr\u00E1z, Franti\u0161ek" . . "RIV/00216208:11320/09:00206906" . "3"^^ . . "Otto, Friedrich" . . . . . "410" . "The degree of word-expansion of lexicalized RRWW-automata - A new measure for the degree of nondeterminism of (context-free) languages"@en . . "2"^^ . "0304-3975" . . . . "The degree of word-expansion of lexicalized RRWW-automata - A new measure for the degree of nondeterminism of (context-free) languages" . "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 occurrences 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." . .