On the Computational Complexity of Dominance Links in Grammatical Formalisms

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 514–524, Uppsala, Sweden, 11-16 July 2010. c⃝2010 Association for Computational Linguistics On the Computational Complexity of Dominance Links in Grammatical Formalisms Sylvain Schmitz LSV, ENS Cachan & CNRS, France sylvain.schmitz@lsv.ens-cachan.fr Abstract Dominance links were introduced grammars to model long distance scram-in bling phenomena, motivating the defi- nition of multiset-valued linear indexed grammars (MLIGs) by Rambow (1994b), and inspiring quite a few recent for- malisms. It turns out that MLIGs have since been rediscovered and reused in a variety of contexts, and that the complex- ity of their emptiness problem has become the key to several open questions in com- puter science. We survey complexity re- sults and open issues on MLIGs and re- lated formalisms, and provide new com- plexity bounds for some linguistically mo- tivated restrictions. 1 Introduction Scrambling constructions, as found in German and other SOV languages (Becker et al., 1991; Ram- bow, 1994a; Lichte, 2007), cause notorious diffi- culties to linguistic modeling in classical grammar formalisms like HPSG or TAG. A well-known il- lustration of this situation is given in the following two German sentences for “that Peter has repaired the fridge today” (Lichte, 2007), dass [Peter] heute [den K¨uhlschrank] repariert hat that Peternom today the fridgeacc repaired has dass [den K¨uhlschrank] heute [Peter] repariert hat that the fridgeacc today Peternom repaired has with a flexible word order between the two com- plements of repariert, namely between the nomi- native Peter and the accusative den K¨uhlschrank. Rambow (1994b) introduced a formalism, un- ordered vector grammars with dominance links (UVG-dls), for modeling such phenomena. These grammars are defined by vectors of context- free productions along with dominance links that                       VP NPnom VP VP NPacc VP VP V repariert Figure 1: A vector of productions for the verb repariert together with its two complements. should be enforced during derivations; for in- stance, Figure 1 shows how a flexible order be- tween the complements of repariert could be ex- pressed in an UVG-dl. Similar dominance mecha- nisms have been employed in various tree descrip- tion formalisms (Rambow et al., 1995; Rambow et al., 2001; Candito and Kahane, 1998; Kallmeyer, 2001; Guillaume and Perrier, 2010) and TAG ex- tensions (Becker et al., 1991; Rambow, 1994a). However, the prime motivation for this survey is another grammatical formalism defined in the same article: multiset-valued linear indexed gram- mars (Rambow, 1994b, MLIGs), which can be seen as a low-level variant of UVG-dls that uses multisets to emulate unfulfilled dominance links in partial derivations. It is a natural extension of Petri nets, with broader scope than just UVG-dls; indeed, it has been independently rediscovered by de Groote et al. (2004) in the context of linear logic, and by Verma and Goubault-Larrecq (2005) in that of equational theories. Moreover, the decid- ability of its emptiness problem has proved to be quite …

Content truncated to 500 words