Abstract
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.