Is there any inherently ambiguous indexed language?

Question

Indexed languages are defined as being produced by an indexed grammar. My question is: Is there an indexed language such that there is no indexed grammar that can produce every word of the language in a unique way (without ambiguity)?

Answer 1

This is an open question, which is explicitly stated in the paper

Adams, Jared; Freden, Eric; Mishna, Marni, From indexed grammars to generating functions, RAIRO, Theor. Inform. Appl. 47, No. 4, 325-350 (2013). ZBL1286.68331.

They also provide some examples which they conjecture to be inherently ambiguous indexed languages:

Consider Crestin’s language of palindrome pairs defined by $L_{Crestin} = \{vw : v, w \in (a|b)^* , v = v^R w = w^R\}$. It is a “worst case” example of an inherently ambiguous context-free language (see [8] and its references). We conjecture that $L_{Crestin}$ remains inherently ambiguous as an indexed language.

A non-contextfree example:

Recall that a word is primitive if it is not a power of another word. In the copious literature on the subject it is customary to let $Q$ denote the language of primitive words over a two letter alphabet. [...]

$L' = \{ w^k : w \in (a|b)^* , k > 1 \}$ defines the complement of $Q$ with respect to the free monoid $(a|b)^*$. It is not difficult to construct an ambiguous balanced grammar for $L'$ [...]. What about an unambiguous grammar? Recall from [20] that $w_1^n = w_2^m$ implies that each $w^i$ is a power of a common word $v$. Thus to avoid ambiguity, each building block $w$ used to construct $L'$ needs to be primitive. This means we must not only be able to recreate $Q$ in order to generate $L$ unambiguously, we must be able to encode each word $w \in Q$ as a string of index symbols, as per the language of composites. We refer again to Section 3.1. We find this highly unlikely and we conjecture that $L' = \{ w^k : w \in (a|b)^* , k > 1\}$ is inherently ambiguous as an indexed language.

For more details and examples, please consult the paper.