next up previous
Next: Challenges and Future Works Up: On NLP Formalisms: from Previous: Global Indexed Grammars

Grammar Comparisons

 

Castaño [4] has pointed out that the main difference among IGs, LIGs, and GIGs, corresponds to the interpretation of the derives relation relative to the behaviour of the stack of indices. In IGs, the stacks of indices are distributed over the non-terminals of the right-hand side of the rule. In this way the same control words can be associated with multiple paths. In LIGs, indices are associated with only one non-terminal at right-hand side of the rule. Thus there is only one non-terminal at right-hand side of the rule. GIGs share this uniqueness of the stack with LIGs: there is only one stack to be considered per derivation. However, the stack of indices in GIGs is independent of non-terminals. Push ruls are constrained to start the right-hand side with a terminal in the GIG definition. The derives definition requires a leftmost derivation for those productions (push and pop rules) that affect the stack of indices.

In NLP field, an important classification was introduced by Joshi [7] - mild context-sensitivity - as a possible model to express the required properties of formalisms that might describe natural language phenomena. Three canonical NLP problems mentioned in the previous section have been addressed mainly because of the inability of generating them with context-free grammars. We give the languages which describe the problems below:

We have seen an IG to generate the multiple agreements language tex2html_wrap_inline1038 in Example 1. LIGs and GIGs can be used to generate tex2html_wrap_inline1038 too with little modification. Castaño [4] provided an example to generate dependent branches with a GIG, which can not be generated by any LIG. We give it in Example 4.

Example 4. (dependent branches) [4]

tex2html_wrap_inline1042

tex2html_wrap_inline1044 where P is:

tex2html_wrap_inline1048, tex2html_wrap_inline1050, tex2html_wrap_inline1052, tex2html_wrap_inline1054

The derivation of aabcdeff:

tex2html_wrap_inline1058

The reason the dependent branches cannot be generated by LIGs stems from the control of the derivation. LIGs' control devices for substrings (non-terminals) are independent of each other, which admits no way of representing relations like n = m + l in dependent branches. On the other hand, GIGs push rules allow substrings to be ``connected''. One analysis done in [5] from the parsing tree aspect gives a very good explanation at this point.

GIGs and LIGs have also been studied and compared with the palindrome language, the copy language, and the multiple dependency language [4]. Consequently, GIGs are capable of generating the copy and multiple dependency languages, where LIGs cannot. One observation has been done is that global indexed languages are mildly context-sensitive languages (MCSLs), which is a characterization of hierarchy of control grammar levels (Weir, 1992). This generalization provides that global indexed languages are second level MCSLs.


next up previous
Next: Challenges and Future Works Up: On NLP Formalisms: from Previous: Global Indexed Grammars

Henry Xiao
Fri Apr 29 18:50:42 EDT 2005