"Otto, Friedrich" . "2"^^ . "A 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 some measures for the degree of nondeterminism of (context-free) languages in terms of lexicalized deterministic restarting automata. These measures are 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 two-dimensional hierarchy of classes of (context-free) languages based on the expansion factor of a language and on the number of different auxiliary symbols available in the underlying characteristic language." . . . "Measure; Degree; Nondeterminism; Context-Free; Languages"@en . "407940" . . "000252061100019" . "A Measure for the Degree of Nondeterminism of Context-Free Languages"@en . "P(1ET100300517), Z(MSM0021620838)" . . "978-3-540-76335-2" . . . . "2007-01-01+01:00"^^ . . "A Measure for the Degree of Nondeterminism of Context-Free Languages" . . . "A Measure for the Degree of Nondeterminism of Context-Free Languages"@en . . . "11320" . "RIV/00216208:11320/07:00206172!RIV10-MSM-11320___" . "Berlin" . "RIV/00216208:11320/07:00206172" . "Berlin" . . . . . . "11"^^ . "Implementation and Application of Automata" . "Springer-Verlag" . "Restarting automata can be seen as analytical variants of classical automata as well as of regulated rewriting systems. We study some measures for the degree of nondeterminism of (context-free) languages in terms of lexicalized deterministic restarting automata. These measures are 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 two-dimensional hierarchy of classes of (context-free) languages based on the expansion factor of a language and on the number of different auxiliary symbols available in the underlying characteristic language."@en . "[AFA190CE49F7]" . . . "Mr\u00E1z, Franti\u0161ek" . "3"^^ . "Pl\u00E1tek, Martin" . . .