TAILIEUCHUNG - Báo cáo khoa học: "On the Computational Complexity of Dominance Links in Grammatical Formalisms"

Dominance links were introduced in grammars to model long distance scrambling phenomena, motivating the definition of multiset-valued linear indexed grammars (MLIGs) by Rambow (1994b), and inspiring quite a few recent formalisms. It turns out that MLIGs have since been rediscovered and reused in a variety of contexts, and that the complexity of their emptiness problem has become the key to several open questions in computer science. We survey complexity results and open issues on MLIGs and related formalisms, and provide new complexity bounds for some linguistically motivated restrictions. . | On the Computational Complexity of Dominance Links in Grammatical Formalisms Sylvain Schmitz LSV ENS Cachan CNRS France Abstract Dominance links were introduced in grammars to model long distance scrambling phenomena motivating the definition of multiset-valued linear indexed grammars MLIGs by Rambow 1994b and inspiring quite a few recent formalisms. It turns out that MLIGs have since been rediscovered and reused in a variety of contexts and that the complexity of their emptiness problem has become the key to several open questions in computer science. We survey complexity results and open issues on MLIGs and related formalisms and provide new complexity bounds for some linguistically motivated restrictions. 1 Introduction Scrambling constructions as found in German and other SOV languages Becker et al. 1991 Rambow 1994a Lichte 2007 cause notorious difficulties to linguistic modeling in classical grammar formalisms like HPSG or TAG. A well-known illustration 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 Kuhlschrank repariert hat that Peternom today the fridgeacc repaired has dass den Kuhlschrank heute Peter repariert hat that the fridgeacc today Peternom repaired has with a flexible word order between the two complements of repariert namely between the nominative Peter and the accusative den Kuhlschrank. Rambow 1994b introduced a formalism unordered 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 VP 74 VP i I NPnom VPy NPacc VP V I repariert Figure 1 A vector of productions for the verb repariert together with its two complements. should be enforced during derivations for instance Figure 1 shows how a flexible order between the complements of repariert could be expressed in an UVG-dl. Similar dominance .

TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.