Article Structure
Abstract
Dominance links were introduced in grammars to model long distance scrambling phenomena, motivating the definition of maltiset—valaed linear indexed grammars (MLIGs) by Rambow (1994b), and inspiring quite a few recent formalisms.
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.
Multiset-Valued Linear Indexed Grammars
Definition 1 (Rambow, 1994b).
Related Formalisms
We review formalisms connected to MLIGs, starting in Section 3.1 with Petri nets and two of their extensions, which turn out to be exactly equivalent to MLIGs.
Computational Complexity
We study in this section the complexity of several decision problems on MLIGs, prominently of emptiness and membership problems, in the general (Section 4.2), k-bounded (Section 4.3), and lexicalized cases (Section 4.4).
Conclusion
Grammatical formalisms with dominance links, introduced in particular to model scrambling phenomena in computational linguistics, have deep connections with several open questions in an unexpected variety of fields in computer science.
Topics
lexicalized
- 2. the effects of two linguistically motivated restrictions on such formalisms, lexicalization and boundedness/rankedness.Page 2, “Introduction”
- Two restrictions on dominance links have been suggested in an attempt to reduce their complexity, sometimes in conjunction: lexicalization and k-boundedness.Page 3, “Multiset-Valued Linear Indexed Grammars”
- We can combine the two restrictions, thus defining the class of k:-bounded lexicalized MLIGs.Page 3, “Multiset-Valued Linear Indexed Grammars”
- Lexicalization Lexicalization in UVG-dls reflects the strong dependence between syntactic constructions (vectors of productions representing an extended domain of locality) and lexical anchors.Page 3, “Multiset-Valued Linear Indexed Grammars”
- A terminal derivation oz =>p to with w in 2* is c-lexicalized for some 0 > 0 if p g c- |w | .1 A MLIG is lexicalized if there exists 0 such that any terminal derivation starting from (S, 20) is c—lexicalized, and we denote by £(MLIGg) the set of lexicalized MLIG languages.Page 3, “Multiset-Valued Linear Indexed Grammars”
- Looking at the grammar of Example 2, any terminal derivation (S, 0) =>p w verifies p = $ + l, and the grammar is thus lexicalized .Page 3, “Multiset-Valued Linear Indexed Grammars”
- 1This restriction is slightly stronger than that of linearly restricted derivations (Rambow, 1994b), but still allows to capture UVG-dl lexicalization .Page 3, “Multiset-Valued Linear Indexed Grammars”
- 3 Adding terminal symbols 0 in each production would result in a lexicalized grammar, still with a non semilinear language.Page 5, “Related Formalisms”
- Lexicalization has now its usual definition: for every vector ({pi,1, .Page 6, “Related Formalisms”
- We study in this section the complexity of several decision problems on MLIGs, prominently of emptiness and membership problems, in the general (Section 4.2), k-bounded (Section 4.3), and lexicalized cases (Section 4.4).Page 6, “Computational Complexity”
- 4.4 Lexicalized CasePage 8, “Computational Complexity”
See all papers in Proc. ACL 2010 that mention lexicalized.
See all papers in Proc. ACL that mention lexicalized.
Back to top.
natural languages
- Natural languages are known for displaying some limited cross-serial dependencies, as witnessed in linguistic analyses, e.g.Page 4, “Multiset-Valued Linear Indexed Grammars”
- Note that we only consider uniform membership, since grammars for natural languages are typically considerably larger than input sentences, and their influence can hardly be neglected.Page 7, “Computational Complexity”
- A conclusion with a more immediate linguistic value is that MLIGs and UVG—dls hardly qualify as formalisms for mildly context-sensitive languages, claimed by Joshi (1985) to be adequate for modeling natural languages , and “roughly” defined as the extensions of context-free languages that displayPage 9, “Conclusion”
See all papers in Proc. ACL 2010 that mention natural languages.
See all papers in Proc. ACL that mention natural languages.
Back to top.
