We present Global Index Grammars, a grammar formalism that uses a stack of indices associated to its productions. This formalism
has restricted context-sensitive descriptive power. The recognition problem for this class of grammars is polynomial: the
time complexity of the algorithm presented here is O(n
6).
See for example [21], [8], [12], [10], among others.
There are many other equivalent or similar formalisms such as, range concatenation grammars, multiple context-free grammars[20], minimalist grammars[22].
See for example, [16], [26], [17].
Similar hierarchies: multiple CFGs [20], multi-push down automata [6].