Global index grammar
Global index grammars (GIGs) are a class of grammars introduced in Castaño (2004) in order to model a number of phenomena, including natural language grammar and genome grammar. The easiest description of GIGs is by comparison to Indexed grammars. Whereas in indexed grammars, a stack of indices is associated with each nonterminal symbol, and can vary from one to another depending on the course of the derivation, in a GIG, there is a single global index stack that is manipulated in the course of the derivation (which is strictly leftmost for any rewrite operation that pushes a  symbol to the stack). Because of the existence of a global stack, a GIG derivation is considered complete when there are no non-terminal symbols left to be rewritten, and the stack is empty. Rule Description. GIG rules come in essentially four forms: rules that do something unconditionally, rules that do something conditioned on the topmost symbol of the stack, rules that push to the stack, and rules that pop from the stack. We can notate these in turn as: where f is any index symbol, is any string of terminals and/or non-terminal symbols, and x is a terminal  is a terminal symbol. Because occasionally a rewrite rule might need to be conditioned on the stack being in some sense "empty", the symbol "#" is used as the bottom-most stack symbol, meaning an "empty" stack contains exactly one symbol, "#". The third rule form, the push rule, should be pointed out, as it differs from the pop rule in requiring that all push operations introduce at least one new terminal symbol to the derivation string. Without this constraint, the class of grammars would be Type-0 and thus Turing Complete. Example. For this example, we will denote steps in the derivation  by placing the derivation string over a stack, as in formula_1. GIGs (but not trGIGs as below) can generate the non-indexed language formula_2 using the following grammar: A derivation for the string is as follows: A similar derivation follows for ', ', and other such sentences. Computational Power. The global index languages are a subset of the context sensitive languages, and a superset of the context free languages. It is known that GIGs can generate the MIX/Bach language formula_14, where "p" is the string permutation function, which is conjectured (but not proven) not to be representable as an indexed language . It is not known whether or not all IGs are also GIGs. It is entirely possible that GIGs and IGs describe merely-overlapping subsets of the CSLs. trGIGs. A subclass of GIGs is the class of trGIGs, which make the pop and push rules uniform, by requiring that pop rules also introduce at least one terminal symbol into the derivation. Example. An example of such a grammar, characterizing the language formula_15, is: The derivation for the string is then: