Article Structure
Abstract
Recently, it was shown (KUHLMANN, SATTA: Tree-adjoining grammars are not closed under strong lexicalization.
Introduction
Tree adjoining grammars [TAG] (Joshi et a1., 1969; Joshi et a1., 1975) are a mildly context-sensitive grammar formalism that can handle certain nonlocal dependencies (Kuhlmann and Mohl, 2006), which occur in several natural languages.
Notation
We write for the set E N | 1 S i S k}, where N denotes the set of nonnegative integers.
Context-free tree grammars
In this section, we recall linear and nondeleting context-free tree grammars [CFTG] (Rounds, 1969; Rounds, 1970).
Normal forms
In this section, we first recall an existing normal form for CFTG.
Lexicalization
In this section, we present the main lexicalization step, which lexicalizes non-monic productions.
Topics
lexicalization
- Recently, it was shown (KUHLMANN, SATTA: Tree-adjoining grammars are not closed under strong lexicalization .Page 1, “Abstract”
- Thus, simple context-free tree grammars strongly lexicalize tree adjoining grammars and themselves.Page 1, “Abstract”
- A good overview on TAG, their formal properties, their linguistic motivation, and their applications is presented by Joshi and Schabes (1992) and Joshi and Schabes (1997), in which also strong lexicalization is discussed.Page 1, “Introduction”
- In general, lexicalization is the process of transforming a grammar into an equivalent one (potentially expressed in another formalism) such that each production contains a lexical item (or anchor).Page 1, “Introduction”
- alphabet, each production of a lexicalized grammar produces at least one letter of the generated string.Page 1, “Introduction”
- Consequently, lexicalized grammars offer significant parsing benefits (Schabes et al., 1988) as the number of applications of productions (i.e., derivation steps) is clearly bounded by the length of the input string.Page 1, “Introduction”
- Correspondingly, we obtain weak and strong lexicalization based on the required equivalence.Page 1, “Introduction”
- The GREIBACH normal form shows that CFG can weakly lexicalize themselves, but they cannot strongly lexicalize themselves (Schabes, 1990).Page 1, “Introduction”
- It is a prominent feature of tree adjoining grammars that they can strongly lexicalize CFG (Schabes, 1990),2 and it was claimed and widely believed that they can strongly lexicalize themselves.Page 1, “Introduction”
- Recently, Kuhlmann and Satta (2012) proved that TAG actually cannot strongly leXicalize themselves.Page 1, “Introduction”
- In fact, they prove that TAG cannot even strongly lexicalize the weaker tree insertion grammars (Schabes and Waters, 1995).Page 1, “Introduction”
See all papers in Proc. ACL 2012 that mention lexicalization.
See all papers in Proc. ACL that mention lexicalization.
Back to top.
