Linear Indexed Grammars

 

Although IGs are proved to share many of context-free languages' properties including the decidability, IGs are not semilinear, which are computationally inefficient in the sense that the decidability can not be solved in polynomial time deterministically. LIGs are derived to meet this requirement from modifying IGs.

A LIG is still defined as a 5-tuple (N, T, I, P, S). The difference with IG definition is that index set I contains the stack of indices, which can be ``transmitted'' only to one non-terminal. So P is a finite set of productions of the form:

• a.
• b. , where i is in I.
• c.

Note that cannot be in I anymore.

Example 2. and P is:

1. 
2. 
3. 
4. 
5. 
6. 

Depending on the choice of 1 or 2, we may end up with aca or bcb (i.e., either consume index i or j). Thus, .

LIGs are semilinear and polynomial parsable. The problem with LIGs is that it significantly reduces the descriptive power from IGs as we can see from the definition above. The formalism of LIGs is very intuitive given IGs'. It is obvious that linear indexed languages are proper subset of indexed languages, and thus a proper subset of context-sensitive languages. The same argument as in IGs can show that all context-free languages are also contained in linear indexed languages.