Sublogarithmic ambiguity

AbstractContext-free grammars and languages with infinite ambiguity can be distinguished by the growth rate of their ambiguity with respect to the length of the words. So far the least growth rate known for a divergent inherent ambiguity function was logarithmic. Roughly speaking we show that it is possible to stay below any computable function. More precisely let f:N→N be an arbitrary computable divergent total non-decreasing function. Then there is a context-free language L with a divergent inherent ambiguity function g below f, i.e., g(n)⩽f(n) for each n∈N. This result is an immediate consequence of two other results which are of independent interest. The first result says that there is a linear context-free grammar G with so called unambiguous turn position whose ambiguity function is below f. The second one states that any ambiguity function of a cycle-free context-free grammar is an inherent ambiguity function of some context-free language