Lambek grammar

This paper presents a method for parsing associative Lambek grammars based on graphtheoretic properties. Connection graphs, which are a simplified version of proof-nets, are actually a mere conservative extension of the earlier method of syntactic connexion, discovered by Ajduckiewicz [1935]. The method amounts to find alternating spanning trees in graphs. A sketch of an algorithm for finding such a tree is provided. Interesting properties of time-complexity for this method are expected.

8p buncha_1 08-05-2013 47 1   Download

Certain phenomena resist coverage within the Lambek Calculus, such as scopeambiguity and non-peripheral extraction. I have argued in previous work that an extension called Polymorphic Lambek Calculus (PLC), which adds variables and their universal quantification, covers these phenomena. However, a major problem is the absence of a known decision procedure for PLC grammars. This paper proposes a decision procedure which covers a subset of all the possible PLC grammars, a subset which, however, includes the PLC grammars with wide coverage. ...

10p buncha_1 08-05-2013 39 2   Download

Use of Lambek's (1958) categorial grammar for linguistic work has generally been rather limited. There appear to be two main reasons for this: the notations most commonly used can sometimes obscure the structure of proofs and fail to clearly convey linguistic structure, and the cMculus as it stands is apparently not powerful enough to describe many phenomena encountered in natural language. In this paper we suggest ways of dealing with both these deficiencies.

6p buncha_1 08-05-2013 52 2   Download

it follows as a theorem from a set of axioms and inference rules. Especially by the work of Van Benthem (1986) and Moortgat (1988) this view, which we will name with Moortgat (1987a) Lambek Theorem Proving (LTP; Lambek, 1958), has become popular among a number of linguists. The descriptive power of LTP can be extended if unification (Shieber, 1986) is added. Several theories have been developed that combine categorial formalisms and unification based formalisms. Within Unification Categorial Grammar (UCG, Calder et al., 1988, Zeevat et al.

7p buncha_1 08-05-2013 32 1   Download

From a processing point of view, however, flexible categorial systems are problematic, since they introduce spurious ambiguity. In this paper, we present a flexible categorial grammar which makes extensive use of the product-operator, first introduced by Lambek (1958). The grammar has the property that for every reading of a sentence, a strictly left-branching derivation can be given. This leads to the definition of a subset of the grammar, for which the spurious ambiguity problem does not arise and efficient processing is possible. ...

8p buncha_1 08-05-2013 46 1   Download

Recent work has seen the emergence of a common framework for parsing categorial grammar (CG) formalisms that fall within the 'type-logical' tradition (such as the Lambek calculus and related systems), whereby some method of linear logic theorem proving is used in combination with a system of labelling that ensures only deductions appropriate to the relevant grammatical logic are allowed. The approaches realising this framework, however, have not so far addressed the task of incremental parsing - - a key issue in earlier work with 'flexible' categorial grammars.

8p bunthai_1 06-05-2013 61 3   Download

In (Kanazawa, 1998) it was shown that rigid Classical Categorial Grammars are learnable (in the sense of (Gold, 1967)) from strings. Surprisingly there are recent negative results for, among others, rigid associative Lamb ek (L) grammars. In this paper the non-lcarnability of the class of rigid grammars in LP (Associative-Commutative Lambek calculus) and LP0 (same, but allowing the empty sequent in derivations) will be shown.

8p bunthai_1 06-05-2013 43 2   Download

We discuss algorithms for generation within the Lambek Theorem Proving Framework. Efficient algorithms for generation in this framework take a semantics-driven strategy. This strategy can be modeled by means of rules in the calculus that are geared to generation, or by means of an algorithm for the Theorem Prover. The latter possibility enables processing of a bidirectional calculus. Therefore Lambek Theorem Proving is a natural candidate for a 'uniform' architecture for natural language parsing and generation.

7p bungio_1 03-05-2013 53 1   Download

The logic behind parsers for categorial grammars can be formalized in several different ways. Lambek Calculus (LC) constitutes an example for a natural deduction 1 style parsing method. In natural language processing, the task of a parser usually consists in finding derivations for all different readings of a sentence. The original Lambek Calculus, when it is used as a parser/theorem prover, has the undesirable property of allowing for the derivation of more than one proof for a reading of a sentence, in the general case. ...

8p bungio_1 03-05-2013 44 1   Download

We study the computational complexity of the parsing problem of a variant of Lambek Categorial Grammar that we call semidirectional. In semidirectional Lambek calculus SD[ there is an additional nondirectional abstraction rule allowing the formula abstracted over to appear anywhere in the premise sequent's left-hand side, thus permitting non-peripheral extraction. SD[ grammars are able to generate each context-free language and more than that. We show that the parsing problem for semidireetional Lambek Grammar is NP-complete by a reduction of the 3Partition problem. ...

6p bunmoc_1 20-04-2013 40 2   Download

This paper compares the consislencybased account of agreement phenomenaing sections up to the conclusion discusses an important difference between the two approaches. 2 Features Grammar in Lambek Categorial in 'unification-based' grammars with an implication-based account based on a simple feature extension to Lambek Categorim G r a m m a r (LCG). We show that the LCG treatment accounts for constructions that have been recognized as problematic for 'unification-based' treatments.

7p bunmoc_1 20-04-2013 49 2   Download

We present a new chart parsing method for Lambek grammars, inspired by a method for DTree grammar parsing. The formulae of a Lambek sequent are firstly converted into rules of an indexed grammar formalism, which are used in an Earley-style predictive chart algorithm. The method is non-polynomial, but performs well for practical purposes - - much better than previous chart methods for Lambek grammars.

8p bunrieu_1 18-04-2013 47 3   Download

There is currently much interest in bringing together the tradition of categorial grammar, and especially the Lambek calculus (Lambek, 1958), with the more recent paradigm of linear logic (Girard, 1987) to which it has strong ties. One active research area concerns the design of non-commutative versions of linear logic (Abrusci, 1991; Rdtor6, 1993) which can be sensitive to word order while retaining the hypothetical reasoning capabilities of standard (commutative) linear logic that make it so well-adapted to handling such phenomena as quantifier scoping (Dalrymple et al., 1995). ...

5p bunrieu_1 18-04-2013 41 2   Download

We provide a logical definition of Minimalist grammars, that are Stabler’s formalization of Chomsky’s minimalist program. Our logical definition leads to a neat relation to categorial grammar, (yielding a treatment of Montague semantics), a parsing-asdeduction in a resource sensitive logic, and a learning algorithm from structured data (based on a typing-algorithm and type-unification). Here we emphasize the connection to Montague semantics which can be viewed as a formal computation of the logical form. ...

8p bunrieu_1 18-04-2013 47 5   Download

This paper is concerned with learning categorial grammars in Gold’s model. In contrast to k-valued classical categorial grammars, k-valued Lambek grammars are not learnable from strings. This result was shown for several variants but the question was left open for the weakest one, the non-associative variant NL. We show that the class of rigid and kvalued NL grammars is unlearnable from strings, for each k; this result is obtained by a specific construction of a limit point in the considered class, that does not use product operator. ...

8p bunbo_1 17-04-2013 42 2   Download