Catálogo de publicaciones - libros

The Minimalist Grammars (MGs) proposed by Stabler(1997) have tree-shaped derivations (Harkema, 2001b; Michaelis, 2001a). As in categorial grammars, each lexical item is an association between a vocabulary element and complex of features, and so the ”yields” or ”fringes” of the derivation trees are sequences of these lexical items, and the string parts of these lexical items are reordered in the course of the derivation. This paper shows that while the derived string languages can be ambiguous and non-context-free, the set of yields of the derivation trees is always context-free and unambiguous. In fact, the derivation yield languages are strictly deterministic context-free languages, which implies that they are LR(0), and that the generation of derivation trees from a yield language string can be computed in linear time. This result suggests that the work of MG parsing consists essentially of guessing the lexical entries associated with words and empty categories.

It is already known that (PMCFG) [1] is an instance of the equivalent formalisms (sLMG) [2, 3] and (RCG) [4, 5]. In this paper we show that by adding the single operation of intersection, borrowed from [6], PMCFG becomes equivalent to sLMG and RCG. As a corollary we get that PMCFG with intersection describe exactly the class of languages recognizable in polynomial time.

Kanazawa has shown that -valued classical categorial grammars have the property of finite elasticity [1], which is a sufficient condition for learnability. He has also partially extended his result to general combinatory grammars, but left open the question of whether some subsets of general combinatory grammars have finite elasticity. We propose a new sufficient condition which implies learnability of some classes of k-valued general combinatory grammars, focusing on the way languages are expressed through a grammatical formalism rather than the classes of languages themselves.

In this paper, we use the logic of partial information to re-examine some early analyses of vague quantifiers in French such as that are found in particular in the work of O. Ducrot [2]. Our approach is based on the paradigm offered by the logical formalization of the sorites paradox. We claim that this paradox offers a general scheme along which the argumentation structure of all vague quantifiers in French may be expressed. We offer a variational principle approximating Grice’s maxims in the case of vague quantification.

The constraint language for lambda structures (CLLS) is a description language for lambda terms. CLLS provides parallelism constraints to talk about the tree structure of lambda terms, and lambda binding constraints to specify variable binding. Parallelism constraints alone have the same expressiveness as context unification. In this paper, we show that lambda binding constraints can also be expressed in context unification when permitting tree regular constraints.

We describe the derivations in a pregroup grammar as the 2-cells of a free compact 2-category defined by the grammar. The 2-cells of this category are the intermediary parsing structures necessary for a semantic interpretation when pregroups are used in natural language processing. The construction of the free compact 2-category also provides another cut-free axiomatisation of compact bilinear logic.

In this paper, an extension of feature constraint logic is presented which allows the coding of errors in feature structures. This is achieved by adding a designated feature to the feature logic with special properties resulting in an expansion of the underlying feature logic. The framework will be formally developed and applied in an ICALL system that allows errors of learners of a foreign-language. Furthermore the system provides an analysis of such errors.

This paper introduces a novel approach to language processing, in which linguistic facts are represented as predicates over ranges of the intput text, usually, but not limited to, ranges of the current sentence. Such an approch allows to build non-linear analyses with a polynomial parsing complexity that take into account simultaneously and with the same technical status morphological, syntactical and semantical properties, this list being non limitative. Classical analyses, such as constituency trees, dependency graphs, topological boxes and predicate-arguments semantics are then obtained as partial projection of a complete analysis. The formalism presented here is based upon Range Concatenation Grammars (hereafter RCG), and has been successfully implemented, thanks to a previously existing RCG parser and a syntactico-semantical grammar for French.

The aim of this paper is to describe an approach to semantic representation in the Lexicalized Tree Adjoining Grammars (LTAG)[1] paradigm. We show how to use all the informations contained in the two representation structures provided by the LTAG formalism in order to provide a dependency graph.

In this paper, we first study the connections between subclasses of AB-categorial grammars and finite state automata. Using this, we explain how learnability results for categorial grammars in Gold’s model from structured positive examples translate into regular grammatical inference results from strings. A closer analysis of the generalization operator used in categorial grammar inference shows that it is strictly more powerful than the one used in usual regular grammatical inference, as it can lead outside the class of regular languages. Yet, we show that the result can still be represented by a new kind of finite-state generative model called a . We prove that every unidirectional categorial grammar, and thus every context-free language, can be represented by such a recursive automaton. We finally identify a new subclass of unidirectional categorial grammars for which learning from strings is not more expensive than learning from structures. A drastic simplification of Kanazawa’s learning algorithm from strings for this class follows.