• Jens Michaelis & Christian Wartena. Unidirectional Inheritance of Indices. A Weakly Context Free Facet of LIGs. Appeared in G. Bouma, G.J.M. Kruijff, and R.T. Oehrle (eds.), Proceedings of the FHCG'98, pp. 258-267. Joint Conference on Formal Grammar, Head-Driven Phrase Structure Grammar and Categorial Grammar. Saarbrücken, August 14-16, 1998.

Abstract

In this paper a restricted type of linear indexed grammar (LIG) is defined, called unidirectional indexed grammar (UIG). This is done essentially by demanding that the inheritance of an index stack is either strictly rightmost or strictly leftmost as long as the stack is not empty. Although they turn out to be weakly equivalent to context free grammars (CFGs), UIGs give rise to structural descriptions that are not generatable by any CFG, but seem to be suitable for linguistic purposes. Moreover, the parsing problem for UIGs is shown to be solvable in $O(n^{3})$-time. Thus, also in this respect, UIGs constitute an interesting restriction of LIGs, the latter known to be of parsing complexity $O(n^{6})$-time in general.

previous page personal homepage