Abstract of Paper

Sublinear Ambiguity
by Klaus Wich

Abstract:

A context-free grammar $G$ is ambiguous iff there is a word that can be
generated by $G$ with at least two different derivation trees. Ambiguous
grammars are often distinguished by their degree of ambiguity, which is the
maximal number of derivation trees for the words generated by them. If there
is no such upper bound $G$ is said to be ambiguous of infinite degree. By
considering how many derivation trees a word of at most length $n$ may have,
we can distinguish context-free grammars with infinite degree of ambiguity
by the growth-rate of their ambiguity with respect to the length of the
words. It is known that each cycle-free context-free grammar $G$ is either
exponentially ambiguous or its ambiguity is bounded by a polynomial. Until
now there have only been examples of context-free languages with inherent
ambiguity $2^{\Theta(n)}$ and $\Theta(n^d)$ for each $d \in\mathbb N_0$. In
this paper first examples of (linear) languages with nonconstant sublinear
ambiguity are presented.