nach oben

2011 | Buch

Kapitel lesen Erstes Kapitel lesen

Logical Aspects of Computational Linguistics

6th International Conference, LACL 2011, Montpellier, France, June 29 – July 1, 2011. Proceedings

herausgegeben von: Sylvain Pogodalla, Jean-Philippe Prost

Verlag: Springer Berlin Heidelberg

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This book constitutes the refereed proceedings of the 6th International Conference on Logical Aspects of Computational Linguistics, LACL 2011, held in Montpellier, France, in June/July 2011. The 18 revised full papers presented were carefully reviewed and selected from 31 submissions. The papers address a wide range of logical and formal methods in computational linguistics such as type-theoretic grammars, dependency grammars, formal language theory, grammatical inference, minimalism, generation, and lexical and formal semantics.

Inhaltsverzeichnis

Frontmatter

Encoding Phases Using Commutativity and Non-commutativity in a Logical Framework

Abstract

This article presents an extension of Minimalist Categorial Grammars (MCG) to encode Chomsky’s phases. These grammars are based on Partially Commutative Logic (PCL) and encode properties of Minimalist Grammars (MG) of Stabler [22]. The first implementation of MCG were using both non-commutative properties (to respect the linear word order in an utterance) and commutative ones (to model features of different constituents). Here, we propose to augment Chomsky’s phases with the non-commutative tensor product of the logic. Then we can give account of the PIC [7] just with logical properties of the framework instead of defining a specific rule.

Maxime Amblard

Using Logic in the Generation of Referring Expressions

Abstract

The problem of generating referring expressions (GRE) is an important task in natural language generation. In this paper, we advocate for the use of logical languages in the output of the content determination phase (i.e., when the relevant features of the object to be referred are selected). Many different logics can be used for this and we argue that, for a particular application, the actual choice shall constitute a compromise between expressive power (how many objects can be distinguished), computational complexity (how difficult it is to determine the content) and realizability (how often will the selected content be realized to an idiomatic expression). We show that well-known results from the area of computational logic can then be transferred to GRE. Moreover, our approach is orthogonal to previous proposals and we illustrate this by generalizing well-known content-determination algorithms to make them parametric on the logic employed.

Carlos Areces, Santiago Figueira, Daniel Gorín

Polarized Classical Non-associative Lambek Calculus and Formal Semantics

Abstract

While initially motivated for studying natural language syntax, the intuitionistic bias underlying traditional Lambek calculi renders them particularly suitable to a Montagovian formal semantics through the Curry-Howard correspondence. Several recent proposals, however, have departed from the intuitionistic tradition, seeking instead to formulate ‘classical’ Lambek calculi. We show that this classical turn need not come at the cost of the tight connection with formal semantics, concentrating on De Groote and Lamarche’s Classical Non-Associative Lambek calculus (CNL). Our work is founded in Girard’s and Andreoli’s research into polarities and focused proofs, suggesting the definition of polarized CNL, its connection to De Groote and Lamarche’s original proposal explicated through the use of phase spaces. We conclude with a discussion of related literature, particularly Moortgat’s Lambek-Grishin calculus.

Arno Bastenhof

The Product-Free Lambek-Grishin Calculus Is NP-Complete

Abstract

The Lambek-Grishin calculus LG is the symmetric extension of the non-associative Lambek calculus NL. In this paper we prove that the derivability problem for the product-free fragment of LG is NP-complete, thus improving on Bransen (2010) where this is shown for LG with product.

Jeroen Bransen

Copredication, Quantification and Frames

Abstract

We propose a record type theoretical account of cases of copredication which have motivated the introduction of dot types in the Generative Lexicon ([2,1]). We will suggest that using record types gives us a general account of dot types and also makes a connection between copredication and the use of hypothetical contexts in a record type theoretic analysis of dynamic generalized quantifiers. We propose a view of lexical innovation which draws both on Pustejovsky’s original work on the Generative Lexicon ([27]) and the notion of resource in [23,15]. We will also address issues relating to counting objects in terms of their aspects which are raised in [1].

Robin Cooper

On Dispersed and Choice Iteration in Incrementally Learnable Dependency Types

Abstract

We study learnability of Categorial Dependency Grammars (CDG), a family of categorial grammars expressing all kinds of projective, discontinuous and repeatable dependencies. For these grammars, it is known that they are not learnable from dependency structures.

We propose two different ways of modelling the repeatable dependencies through iterated types and the two corresponding families of CDG which cannot distinguish between the dependencies repeatable at least K times and those repeatable any number of times. For both we show that they are incrementally learnable in the limit from dependency structures.

Denis Béchet, Alexandre Dikovsky, Annie Foret

Closure Properties of Minimalist Derivation Tree Languages

Abstract

Recently, the question has been raised whether the derivation tree languages of Minimalist grammars (MGs; [14, 16]) are closed under intersection with regular tree languages [4, 5]. Using a variation of a proof technique devised by Thatcher [17], I show that even though closure under intersection does not obtain, it holds for every MG and regular tree language that their intersection is identical to the derivation tree language of some MG modulo category labels. It immediately follows that the same closure property holds with respect to union, relative complement, and certain kinds of linear transductions. Moreover, enriching MGs with the ability to put regular constraints on the shape of their derivation trees does not increase the formalism’s weak generative capacity. This makes it straightforward to implement numerous linguistically motivated constraints on the Move operation.

Thomas Graf

Well-Nestedness Properly Subsumes Strict Derivational Minimalism

Abstract

Minimalist grammars (MGs) constitute a mildly context-sensitive formalism when being equipped with a particular locality condition (LC), the shortest move condition. In this format MGs define the same class of derivable string languages as multiple context-free grammars (MCFGs). Adding another LC to MGs, the specifier island condition (SPIC), results in a proper subclass of derivable languages. It is rather straightforward to see this class is embedded within the class of languages derivable by some well-nested MCFG (MCFG _wn ). In this paper we show that the embedding is even proper. We partially do so adapting the methods used in [13] to characterize the separation of MCFG _wn-languages from MCFG-languages by means of a “simple copying” theorem. The separation of strict derivational minimalism from well-nested MCFGs is then characterized by means of a “simple reverse copying” theorem. Since for MGs, well-nestedness seems to be a rather ad hoc restriction, whereas for MCFGs, this holds regarding the SPIC, our result may suggest we are concerned here with a structural difference between MGs and MCFGs which cannot immediately be overcome in a non-stipulated manner.

Makoto Kanazawa, Jens Michaelis, Sylvain Salvati, Ryo Yoshinaka

Minimalist Tree Languages Are Closed Under Intersection with Recognizable Tree Languages

Abstract

Minimalist grammars are a mildly context-sensitive grammar framework within which analyses in mainstream chomskyian syntax can be faithfully represented. Here it is shown that both the derivation tree languages and derived tree languages of minimalist grammars are closed under intersection with regular tree languages. This allows us to conclude that taking into account the possibility of ‘semantic crashes’ in the standard approach to interpreting minimalist structures does not alter the strong generative capacity of the formalism. In addition, the addition to minimalist grammars of complexity filters is easily shown using a similar proof method to not change the class of derived tree languages.

Gregory M. Kobele

Do Dialogues Have Content?

Abstract

In this paper, the notion of “the content of a dialogue” is shown to be problematic in light of the phenomena of semantic coordination in dialogue, and the associated notion of semantic plasticity – the ability of meanings to change as a result of language use. Specifically, it appears that any notion of content in dialogue based on classical model-theoretical semantics will be insufficient for capturing semantic plasticity. An alternative formal semantics, type theory with records (TTR) is briefly introduced and is show to be better equipped to deal with semantic coordination and plasticity. However, it is also argued that any account of content in dialogue which takes semantic coordination seriously will also need to consider the problems it raises for some concepts central to traditional notions of meaning, namely inference and truth.

Staffan Larsson

Contextual Analysis of Word Meanings in Type-Theoretical Semantics

Abstract

Word meanings are context sensitive and may change in different situations. In this paper, we consider how contexts and the associated contextual meanings of words may be represented in type-theoretical semantics, the formal semantics based on modern type theories. It is shown, in particular, that the framework of coercive subtyping provides various useful tools in the representation.

Zhaohui Luo

Logic Programming of the Displacement Calculus

Abstract

The displacement calculus of Morrill, Valentín and Fadda (2011)[12] forms a foundation for type logical categorial grammar in which discontinuity is accommodated alongside continuity in a logic which is free of structural rules and which enjoys Cut-elimination, the subformula property, decidability, and the finite reading property. The calculus deploys a new kind of sequent calculus which we call hypersequent calculus in which types and configurations have not only external context but also internal context, in the case that they are discontinuous. In this paper we consider the logic programming of backward chaining hypersequent proof search for the displacement calculus. We show how focusing eliminates all spurious ambiguity in the fragment without antecedent tensors and we illustrate coding of the essential features of displacement. In this way we lay a basis for parsing/theorem proving for this calculus, which is being used and extended in a system CatLog currently under development.

Glyn Morrill

Conditional Logic C b and Its Tableau System

Abstract

Conditional logic is a kind of modal logic for analyzing the truth conditions and inferences of conditional sentences in natural language. However, it has been pointed out in the literature that empirical problems plague all of the previously proposed conditional logics. Moreover, C ₁ and C ₂ are defined by imposing certain restrictions on their Kripke frames, and there exist no corresponding proof systems.

In order to solve these problems, we propose a new system of conditional logic, which we call C _b. C _b is an extension of C ⁺ through the addition of new rules on accessibility, and it has a corresponding tableau system. We show that C _b has empirical advantages over C ₁ and C ₂ as a model of inference in natural language, and compare it with other proof systems of conditional logic.

Yuri Ozaki, Daisuke Bekki

Are (Linguists’) Propositions (Topos) Propositions?

Abstract

Lambek([22]) proposed a categorial achitecture for natural language grammars, whereby syntax and semantics are modelled by a biclosed monoidal category (bmc) and a cartesian closed category (ccc) respectively, and semantic interpretation by a functor from syntax to semantics that preserves the biclosed monoidal structure; essentially this same architecture underlies the framework of abstract categorial grammar (ACG, de Groote [12]), except that the bmc is now symmetric, in keeping with the collapsing of Lambek’s directional implications / and \ into the linear implication \(\multimap\). At the same time, Lambek proposed that the semantic ccc bears the additional structure of a topos, and that the meanings of declarative sentences—linguist’s propositions—can be identified with propositions in the sense of topos theory, i.e. morphisms from the terminal object 1 to the subobject classifier Ω. Here we show (1) that this proposal as it stands is untenable, and (2) that a serviceable framework results if a preboolean algebra object distinct from Ω is employed instead. Additionally we show that the resulting categorial structure provides ‘for free’, via Stone duality, an account of the relationship between fine-grained ‘hyperintensional’ semantics ([6],[33],[27],[28]) and the familiar coarse-grained intensional semantics of Carnap ([2]) and Montague ([26]).

Carl Pollard

Event in Compositional Dynamic Semantics

Abstract

We present a framework which constructs an event-style discourse semantics. The discourse dynamics are encoded in continuation semantics and various rhetorical relations are embedded in the resulting interpretation of the framework. We assume discourse and sentence are distinct semantic objects, that play different roles in meaning evaluation. Moreover, two sets of composition functions, for handling different discourse relations, are introduced. The paper first gives the necessary background and motivation for event and dynamic semantics, then the framework with detailed examples will be introduced.

Sai Qian, Maxime Amblard

Using Tree Transducers for Grammatical Inference

Abstract

We present a novel way of extracting a categorial grammar from annotated data. Using the sentences from the Paris VII annotated treebank [2] as our starting point, we use a tree transducer to convert the annotated trees from the corpus into categorial grammar derivations.

We describe both the formal aspects and the implementation of the tree transducer, which is a conservative extension of standard tree transducers allowing a compact specification of the transductions rules relevant for our purposes, and we discuss the specific set of transduction rules we use to convert the corpus into AB grammar derivation trees.

Evaluating the resulting tree transducer on the entire corpus, we find that it produces a treebank finds lexical entries for 90,0% of the corpus, though it produces complete derivations for only 75% of all sentence in the corpus.

Noémie-Fleur Sandillon-Rezer, Richard Moot

Distributional Learning of Abstract Categorial Grammars

Abstract

Recent studies on grammatical inference have demonstrated the benefits of the learning strategy called “distributional learning” for context-free and multiple context-free languages. This paper gives a comprehensive view of distributional learning of “context-free” formalisms (roughly in the sense of Courcelle 1987) in terms of abstract categorial grammars, in which existing “context-free” formalisms can be encoded.

Ryo Yoshinaka, Makoto Kanazawa

Some Generalised Comparative Determiners

Abstract

Functions denoted by specific comparative expressions called generalised comparative determiners are analysed. These expressions form verb arguments when applied to common nouns. They denote functions which take sets and a binary relation as argument and give a set as result. These functions are thus different from denotations of ”ordinary” determiners. However, they do obey some similar constraints, properly generalised. It is shown that verbal arguments obtained from such generalised determiners extend the expressive power of NLs since functions that they denote are not just case extensions of type 〈1〉 quantifiers used to interpret ”ordinary” determiner phrases.

Richard Zuber

Backmatter

Titel: Logical Aspects of Computational Linguistics
herausgegeben von: Sylvain Pogodalla
Jean-Philippe Prost
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-642-22221-4
Print ISBN: 978-3-642-22220-7
DOI: https://doi.org/10.1007/978-3-642-22221-4