"11320" . "SG - Singapursk\u00E1 republika" . . "RIV/00216208:11320/07:00004065" . . . "[37D6A4200D45]" . "Mr\u00E1z, Franti\u0161ek" . . . "0129-0541" . "Restarting automata can be considered as a machine model as well as regulated rewriting systems. We introduce a measure of ambiguity for restarting automata which recognizes a language as a projection of its characteristic language (containing also auxiliarynon-inputsymbols) into its input alphabet. Based on this measure we define an ambiguity measure of languages. This measure can be considered as a measure of non-determinism of languages. We show that there is an infinite hierarchy with respect to the degree of ambiguity even inside linear languages and that there are linear languages with a linear ambiguity." . "Restarting automata can be considered as a machine model as well as regulated rewriting systems. We introduce a measure of ambiguity for restarting automata which recognizes a language as a projection of its characteristic language (containing also auxiliarynon-inputsymbols) into its input alphabet. Based on this measure we define an ambiguity measure of languages. This measure can be considered as a measure of non-determinism of languages. We show that there is an infinite hierarchy with respect to the degree of ambiguity even inside linear languages and that there are linear languages with a linear ambiguity."@en . "6" . "Vol. 18" . "Ambiguity; restarting; automata"@en . "International Journal of Foundations of Computer Science" . "V\u00EDcezna\u010Dnost pomoc\u00ED restartovac\u00EDch automat\u016F"@cs . "Ambiguity by restarting automata"@en . . . . . "RIV/00216208:11320/07:00004065!RIV08-AV0-11320___" . "Restartovac\u00ED automaty lze studovat jako automaty i jako regulovan\u00E9 p\u0159episovac\u00ED syst\u00E9my. V pr\u00E1ci se zav\u00E1d\u00ED m\u00EDra v\u00EDcezna\u010Dnosti pro restartovac\u00ED automaty, kter\u00E9 rozpozn\u00E1vaj\u00ED jazyky pomoc\u00ED projekce z jejich charakteristick\u00FDch jazyk\u016F (obsahuj\u00EDc\u00EDch t\u00E9\u017E pomocn\u00E9 symboly) na jazyky slo\u017Een\u00E9 pouze ze vstupn\u00EDch symbol\u016F. Na t\u00E9to m\u00ED\u0159e je zalo\u017Eena m\u00EDra v\u00EDcezna\u010Dnosti jazyk\u016F. Je uk\u00E1z\u00E1no, \u017Ee tuto m\u00EDru lze pova\u017Eovat za m\u00EDru nedeterminismu jazyk\u016F. Hlavn\u00EDm v\u00FDsledkem je d\u016Fkaz existence nekone\u010Dn\u00E9 \u0161k\u00E1ly t\u0159\u00EDd jazyk\u016F podle stupn\u011B jejich v\u00EDcezna\u010Dnosti a existence jazyk\u016F s line\u00E1rn\u00ED vzr\u016Fstem v\u00EDcezna\u010Dnosti s ohledem na r\u016Fst d\u00E9lky jejich v\u011Bt (slov)."@cs . "Ambiguity by restarting automata" . "Ambiguity by restarting automata"@en . "409209" . . . "Ambiguity by restarting automata" . "10"^^ . . "3"^^ . "Pl\u00E1tek, Martin" . . "2"^^ . . "V\u00EDcezna\u010Dnost pomoc\u00ED restartovac\u00EDch automat\u016F"@cs . . "P(1ET100300517), Z(MSM0021620838)" . . . "1343;1352" . .