nach oben

2012 | Buch

Kapitel lesen Erstes Kapitel lesen

Logical Aspects of Computational Linguistics

7th International Conference, LACL 2012, Nantes, France, July 2-4, 2012. Proceedings

herausgegeben von: Denis Béchet, Alexander Dikovsky

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

Edited in collaboration with FoLLI, the Association of Logic, Language and Information, this book constitutes the refereed proceedings of the 7th International Conference on Logical Aspects of Computational Linguistics, LACL 2012, held in Nantes, France, in July 2012. The 15 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 24 submissions. The papers are organized in topical sections on logical foundation of syntactic formalisms, logics for semantics of lexical items, sentences, discourse and dialog, applications of these models to natural language processing, type theoretic, proof theoretic, model theoretic and other logically based formal methods for describing natural language syntax, semantics and pragmatics, as well as the implementation of natural language processing software relying on such methods.

Inhaltsverzeichnis

Frontmatter

Logical Grammars, Logical Theories

Abstract

Residuated lattices form one of the theoretical backbones of the Lambek Calculus as the standard free models. They also appear in grammatical inference as the syntactic concept lattice, an algebraic structure canonically defined for every language L based on the lattice of all distributionally definable subsets of strings. Recent results show that it is possible to build representations, such as context-free grammars, based on these lattices, and that these representations will be efficiently learnable using distributional learning. In this paper we discuss the use of these syntactic concept lattices as models of Lambek grammars, and use the tools of algebraic logic to try to link the proof theoretic ideas of the Lambek calculus with the more algebraic approach taken in grammatical inference. We can then reconceive grammars of various types as equational theories of the syntactic concept lattice of the language. We then extend this naturally from models based on concatenation of strings, to ones based on concatenations of discontinuous strings, which takes us from context-free formalisms to mildly context sensitive formalisms (multiple context-free grammars) and Morrill’s displacement calculus.

Alexander Clark

Ludics and Natural Language: First Approaches

Abstract

Ludics is a rebuilding of Linear Logic from the sole concept of interaction on objects called designs, that abstract proofs. Works have been done these last years to reconsider the formalization of Natural Language: a dialogue may be viewed as an interaction between such abstractions of proofs. We give a few examples taken from dialogue modeling but also from semantics or speech acts to support this approach.

Christophe Fouqueré, Myriam Quatrini

The Non Cooperative Basis of Implicatures

Abstract

This paper presents and addresses a problem in pragmatics concerning the inference of implicatures within a Gricean framework. I propose a model in which implicatures are reasonable even in the absence of the sort of strong cooperativity supposed by Griceans.

Nicholas Asher

Movement-Generalized Minimalist Grammars

Abstract

A general framework is presented that allows for Minimalist grammars to use arbitrary movement operations under the proviso that they are all definable by monadic second-order formulas over derivation trees. Lowering, sidewards movement, and clustering, among others, are the result of instantiating the parameters of this framework in a certain way. Even though weak generative capacity is not increased, strong generative capacity may change depending on the available movement types. Notably, TAG-style tree adjunction can be emulated by a special type of lowering movement.

Thomas Graf

Toward the Formulation of Presupposition by Illative Combinatory Logic

Abstract

Model-theoretic semantics, which originates with Tarski, and proof-thoretic semantics, which originates with Gentzen, are two views in semantics of logic that are distinct from but closely related to each other. Each has advantages over the other in investigating a certain aspect of logic, and it is more or less commonly accepted that rather than being a matter of methodological choice, utilizing them gives us diversified standpoints on various issues. A good example of this is the two proofs of the consistency of LK: one proof is based on soundness and the other on cut-elimination, which makes use of different resources but also together reveals what the consistency of predicate calculus indeed depends on.

Yuri Ishishita, Daisuke Bekki

Abstract Automata and a Normal Form for Categorial Dependency Grammars

Abstract

Categorial Dependency Grammars (CDG) studied in this paper are categorial grammars expressing projective and discontinuous dependencies, stronger than cf-grammars and presumably nonequivalent to mild context-sensitive grammars. We define a normal form of CDG similar to Greibach normal form for cf-grammars and propose an effective algorithm which transforms any CDG into an equivalent CDG in the normal form. A class of push-down automata with independent counters is defined and it is proved that they accept the class of CDG-languages. We present algorithms that transform any CDG into an automaton and vice versa.

Boris Karlov

Importing Montagovian Dynamics into Minimalism

Abstract

Minimalist analyses typically treat quantifier scope interactions as being due to movement, thereby bringing constraints thereupon into the purview of the grammar. Here we adapt De Groote’s continuation-based presentation of dynamic semantics to minimalist grammars. This allows for a simple and simply typed compositional interpretation scheme for minimalism.

Gregory M. Kobele

CoTAGs and ACGs

Abstract

Our main concern is to provide a complete picture of how coTAGs, as a particular variant within the general framework of tree adjoining grammars (TAGs), can be captured under the notion of abstract categorial grammars (ACGs). coTAGs have been introduced by Barker [1] as an “alternative conceptualization” in order to cope with the tension between the TAG-mantra of the “locality of syntactic dependencies” and the seeming non-locality of quantifier scope. We show how our formalization of Barker’s proposal leads to a class of higher order ACGs. By taking this particular perspective, Barker’s proposal turns out as a straightforward extension of the proposal of Pogodalla [11], where the former in addition to “simple” inverse scope phenomena also captures inverse linking and non-inverse linking phenomena.

Gregory M. Kobele, Jens Michaelis

Gapping as Like-Category Coordination

Abstract

We propose a version of Type-Logical Categorial Grammar (TLCG) which combines the insights of standard TLCG (Morrill 1994, Moortgat 1997) in which directionality is handled in terms of forward and backward slashes, and more recent approaches in the CG literature which separate directionality-related reasoning from syntactic combinatorics by means of Ł-binding in the phonological component (Oehrle 1994, de Groote 2001, Muskens 2003). The proposed calculus recognizes both the directionality-sensitive modes of implication (/ and \) of the former and the directionality-insensitive mode of implication tied to phonological Ł-binding in the latter (which we notate here as |).

Empirical support for the proposed system comes from the fact that it enables a straightforward treatment of Gapping, a phenomenon that has turned out to be extremely problematic in the syntactic literature including CG-based approaches.

Yusuke Kubota, Robert Levine

L-Completeness of the Lambek Calculus with the Reversal Operation

Abstract

We extend the Lambek calculus with rules for a unary operation corresponding to language reversal and prove that this calculus is complete with respect to the class of models on subsets of free semigroups (L-models). We also prove that categorial grammars based on this calculus generate precisely all context-free languages without the empty word.

Stepan Kuznetsov

Distributive Full Nonassociative Lambek Calculus with S4-Modalities Is Context-Free

Abstract

We study Nonassociative Lambek Calculus with additives, satisfying the distributive law and S4-modalities. We prove that the categorial grammars based on it, also enriched with assumptions, generate context-free languages. This extends earlier results of Buszkowski [4] for NL (Nonassociative Lambek Calculus), Buszkowski and Farulewski [6] for DNFL (Distributive Full Nonassociative Lambek Calculus) and Plummer [19], [20] for NL_S4 (Nonassociative Lambek Calculus with S4-modalities) without assumptions.

Zhe Lin

Common Nouns as Types

Abstract

When modern type theories are employed for formal semantics, common nouns (CNs) are interpreted as types, not as predicates. Although this brings about some technical advantages, it is worthwhile to ask: what is special about CNs that merits them to be interpreted as types? We discuss the observation made by Geach that, unlike other lexical categories, CNs have criteria of identity, a component of meaning that makes it legitimate to compare, count and quantify. This is closely related to the notion of set (type) in constructive mathematics, where a set (type) is not given solely by specifying its objects, but together with an equality between its objects, and explains and justifies to some extent why types are used to interpret CNs in modern type theories. It is shown that, in order to faithfully interpret modified CNs as Σ-types so that the associated criteria of identity can be captured correctly, it is important to assume proof irrelevance in type theory. We shall also briefly discuss a proposal to interpret mass noun phrases as types in a uniform approach to the semantics of CNs.

Zhaohui Luo

Extractability as the Deduction Theorem in Subdirectional Combinatory Logic

Abstract

The formulation of Combinatory Categorial Grammar (CCG) [7], especially the choice of combinatory rules and their nominatum, strongly imply connection with a typed-version of Combinatory Logic (CL). Since typed CL is a term calculus for an implication fragment of a Hilbert-style proof system, in the sense of the Curry-Howard isomorphism, it seems plausible to regard CCG as a grammar that corresponds to a Hilbert-style proof system, in that the associative Lambek calculus [3] corresponds to a Gentzen-style proof system.

Hiroko Ozaki, Daisuke Bekki

Agnostic Possible Worlds Semantics

Abstract

Working within standard classical higher-order logic, we propose a possible worlds semantics (PWS) which combines the simplicity of the familiar Montague semantics (MS), in which propositions are sets of worlds, with the fine-grainedness of the older but less well-known tractarian semantics (TS) of Wittgenstein and C.I. Lewis, wherein worlds are maximal consistent sets of propositions. The proposed agnostic PWS makes neither montagovian nor tractarian ontological commitments, but is consistent with (and easily extensible to) either alternative (among many others). It is technically straightforward and, we believe, capable of everything linguists need PWS to do, such as interfacing with a logical grammar and serving as a basis for dynamic semantics.

Andrew Plummer, Carl Pollard

Abstract Machines for Argumentation

Abstract

One of the most striking features of ludics is that it provides us with convenient tools for the modelling of interaction. As a consequence, ludics can be employed as a potential framework for the study of dialogues. In this paper we address some of the issues that arise when one tries to model certain types of dialogues that occur in the field of argumentation. We shall exploit that ludics’ designs can be regarded as abstract Böhm trees and explain how the pointer interaction of the associated geometric abstract machine relates to a notion of backtracking.

Kurt Ranalter

On the Completeness of Lambek Calculus with Respect to Cofinite Language Models

Abstract

We give an alternative proof of the fact that the product-free Lambek calculus is complete with respect to cofinite language models. It was first proved by Buszkowski in 1982 by the method of barriers. We use another method, which is also based on the technique of canonical models, to obtain a new proof of this result.

Alexey Sorokin

Dot-types and Their Implementation

Abstract

Dot-types, as proposed by Pustejovsky and studied by many others, are special data types useful in formal semantics to describe interesting linguistic phenomena such as copredication. In this paper, we present an implementation of dot-types in the proof assistant Plastic base on their formalization in modern type theories.

Tao Xue, Zhaohui Luo

Backmatter

Titel: Logical Aspects of Computational Linguistics
herausgegeben von: Denis Béchet
Alexander Dikovsky
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-642-31262-5
Print ISBN: 978-3-642-31261-8
DOI: https://doi.org/10.1007/978-3-642-31262-5

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

Logical Grammars, Logical Theories

Ludics and Natural Language: First Approaches

The Non Cooperative Basis of Implicatures

Movement-Generalized Minimalist Grammars

Toward the Formulation of Presupposition by Illative Combinatory Logic

Abstract Automata and a Normal Form for Categorial Dependency Grammars

Importing Montagovian Dynamics into Minimalism

CoTAGs and ACGs

Gapping as Like-Category Coordination

L-Completeness of the Lambek Calculus with the Reversal Operation

Distributive Full Nonassociative Lambek Calculus with S4-Modalities Is Context-Free

Common Nouns as Types

Extractability as the Deduction Theorem in Subdirectional Combinatory Logic

Agnostic Possible Worlds Semantics

Abstract Machines for Argumentation

On the Completeness of Lambek Calculus with Respect to Cofinite Language Models

Dot-types and Their Implementation

Backmatter

Premium Partner