Global Index Languages

Context-free grammars (CFGs) is perhaps the best understood and most applicable part of formal language theory. However there are many problems that cannot be described by context-free languages: “the world is not context-free” [25]. One of those problems concerns natural language phenomena. There is increasing consensus that modeling certain natural language problems would require more descriptive power than that allowed by context-free languages. One of the hard problems in natural language is coordination. In order to model coordination, it might be necessary to deal with the multiple copies language: {lcub}ww+ |w ∈ &Sgr;*{rcub} [29].; Innumerable formalisms have been proposed to extend the power of context-free grammars. Mildly context-sensitive languages and grammars emerged as a paradigm capable of modeling the requirements of natural languages. At the same time there is a special concern to preserve the ‘nice’ properties of context-free languages: for instance, polynomial parsability and semi-linearity. This work takes these ideas as its goal.; Languages (GILs). This family of languages preserves the desirable properties mentioned above: bounded polynomial parsability, semi-linearity, and at the same time has an “extra” context-sensitive descriptive power (e.g. the “multiple-copies” language is a GI language). GIls descriptive power is shown both in terms of the set of string languages included in GILs, as well as the structural descriptions generated by the corresponding grammars. We present a two-stack automaton model for GILs and a grammar model (Global Index Grammars) in Chapter 2 and 3. Then characterization and representation theorems as well as closure properties are also presented. An Earley type algorithm to solve the recognition problem is discussed in Chapter 5, as well as an LR-parsing algorithm for the deterministic version of GILs. Finally, we discuss in Chapter 6 the relevance of Global Index Languages for natural language phenomena.