Skip to main content

2011 | Buch

Logic, Language, and Computation

8th International Tbilisi Symposium on Logic, Language, and Computation, TbiLLC 2009, Bakuriani, Georgia, September 21-25, 2009. Revised Selected Papers

herausgegeben von: Nick Bezhanishvili, Sebastian Löbner, Kerstin Schwabe, Luca Spada

Verlag: Springer Berlin Heidelberg

Buchreihe : Lecture Notes in Computer Science

insite
SUCHEN

Über dieses Buch

Edited in collaboration with FoLLI, the Association of Logic, Language and Information, this book constitutes the refereed proceedings of the 8th International Tbilisi Symposium on Logic, Language, and Computation, TbiLLC 2009, held in Bakuriani, Georgia, in September 2009. The 20 revised full papers included in the book were carefully reviewed and selected from numerous presentations given at the symposium. The focus of the papers is on the following topics: natural language syntax, semantics, and pragmatics; constructive, modal and algebraic logic; linguistic typology and semantic universals; logics for artificial intelligence; information retrieval, query answer systems; logic, games, and formal pragmatics; language evolution and learnability; computational social choice; historical linguistics, history of logic.

Inhaltsverzeichnis

Frontmatter

Logic and Computation

Ordinal Completeness of Bimodal Provability Logic GLB
Abstract
Bimodal provability logic GLB, introduced by G. Japaridze, currently plays an important role in the applications of provability logic to proof-theoretic analysis. Its topological semantics interprets diamond modalities as derived set operators on a bi-scattered bitopological space. We study the question of completeness of this logic w.r.t. the most natural space of this kind, that is, w.r.t. an ordinal α equipped with the interval topology and with the so-called club topology. We show that, assuming the axiom of constructibility, GLB is complete for any \(\alpha \geq\aleph_\omega \). On the other hand, from the results of A. Blass it follows that, assuming the consistency of “there is a Mahlo cardinal,” it is consistent with ZFC that GLB is incomplete w.r.t. any such space. Thus, the question of completeness of GLB w.r.t. natural ordinal spaces turns out to be independent of ZFC.
Lev Beklemishev
Spectral and T 0-Spaces in d-Semantics
Abstract
In [6] it is shown that if we interpret modal diamond as the derived set operator of a topological space (the so-called d-semantics), then the modal logic of all topological spaces is wK4—weak K4—which is obtained by adding the weak version \(\Diamond\Diamond p\to p\vee\Diamond p\) of the K4-axiom \(\Diamond\Diamond p\to\Diamond p\) to the basic modal logic K.
In this paper we show that the T 0 separation axiom is definable in d-semantics. We prove that the corresponding modal logic of T 0-spaces, which is strictly in between wK4 and K4, has the finite model property and is the modal logic of all spectral spaces—an important class of spaces, which serve as duals of bounded distributive lattices. We also give a detailed proof that wK4 has the finite model property and is the modal logic of all topological spaces.
Guram Bezhanishvili, Leo Esakia, David Gabelaia
A Note on Uniform Interpolation Proofs in Modal Deep Inference Calculi
Abstract
This paper answers one rather particular question: how to perform a proof of uniform interpolation property in deep inference calculi for modal logics. We show how to perform a proof of uniform interpolation property in deep inference calculus for the basic modal logic K via forgetting a variable in a certain normal form constructed by backward proof search. For that purpose we modify the framework of deep-inference calculus using a cover modality on the meta level to structure deep sequents.
Marta Bílková
A Modal Transcription of the Hausdorff Residue
Abstract
The modal system S4.Grz is the system that results when the axiom (Grz) □(□(p → □p) → p) → □p is added to the modal system S4, i. e. S4.Grz = S4 + Grz. The aim of the present note is to prove in a direct way, avoiding duality theory, that the modal system S4.Grz admits the following alternative definition: S4.Grz = S4 + R-Grz, where R-Grz is an additional inference rule:
$$ (R-Grz)\;\;\;\;\;\;\;\;\;\; \frac{\vdash\Box(p \rightarrow \Box p) \rightarrow p}{\vdash p} $$
This rule is a modal counterpart of the following topological condition: If a subset A of a topological space X coincides with its Hausdorff residue ρ(A) then A is empty. In other words the empty set is a unique “fixed” point of the residue operator ρ(·).
We also present some consequences of this alternative axiomatic definition.
Leo Esakia
Jankov’s Theorems for Intermediate Logics in the Setting of Universal Models
Abstract
In this article we prove two well-known theorems of Jankov in a uniform frame-theoretic manner. In frame-theoretic terms, the first one states that for each finite rooted intuitionistic frame there is a formula ψ with the property that this frame can be found in any counter-model for ψ in the sense that each descriptive frame that falsifies ψ will have this frame as the p-morphic image of a generated subframe ([12]). The second one states that KC, the logic of weak excluded middle, is the strongest logic extending intuitionistic logic IPC that proves no negation-free formulas beyond IPC ([13]). The proofs use a simple frame-theoretic exposition of the fact discussed and proved in [4] that the upper part of the n-Henkin model \(\mathcal{H}(n)\) is isomorphic to the n-universal model \(\mathcal{U}(n)\) of IPC. Our methods allow us to extend the second theorem to many logics L for which L and L + KC prove the same negation-free formulas. All these results except the last one earlier occurred in a somewhat different form in [16].
Dick de Jongh, Fan Yang
A View of Canonical Extension
Abstract
This is a short survey illustrating some of the essential aspects of the theory of canonical extensions. In addition some topological results about canonical extensions of lattices with additional operations in finitely generated varieties are given. In particular, they are doubly algebraic lattices and their interval topologies agree with their double Scott topologies and make them Priestley topological algebras.
Mai Gehrke, Jacob Vosmaer
Intuitionistic Sequent-Style Calculus with Explicit Structural Rules
Abstract
In this paper we extend the Curry-Howard correspondence to intuitionistic sequent calculus with explicit structural rules of weakening and contraction. We present a linear term calculus derived from the calculus of Espírito Santo, which captures the computational content of the intuitionistic sequent logic, by adding explicit operators for weakening and contraction. For the proposed calculus we introduce the type assignment system with simple types and prove some operational properties, including the subject reduction and strong normalisation property. We then relate the proposed linear type calculus to the simply typed intuitionistic calculus of Kesner and Lengrand, which handles explicit operators of weakening and contraction in the natural deduction framework.
Silvia Ghilezan, Jelena Ivetić, Pierre Lescanne, Dragisa Žunić
Efficient Design and Inference in Distributed Bayesian Networks: An Overview
Abstract
This paper discusses an approach to distributed Bayesian modeling and inference, which is relevant for an important class of contemporary real world situation assessment applications. By explicitly considering the locality of causal relations, the presented approach (i) supports coherent distributed inference based on large amounts of very heterogeneous information, (ii) supports a systematic validation of distributed models and (iii) can be robust with respect to the modeling deviations of parameters. The challenges of distributed situation assessment applications and their solutions are explained with the help of a real world example from the gas monitoring domain.
Patrick de Oude, Frans C. A. Groen, Gregor Pavlin
Logic of Questions and Public Announcements
Abstract
This paper aims to explore the role of questions in communication in a group of cooperative rational agents. Using epistemic representation of questions proposed in [6] we employ the framework of public announcement logic to explore the flow of information in the process of asking and replying questions in a group. We show that some of the erotetic notions we introduce nicely correspond to the standard epistemic ones.
Michal Peliš, Ondrej Majer
Boolean Modal Logic wK4 Dyn - Doxastic Interpretation
Abstract
We consider the Boolean modal logic wK4 Dyn for which we prove topological and Kripke completeness results. The main result is to show that wK4 Dyn is expressively equivalent to the extended language with common belief and distributed belief operators over the class of all weakly transitive, regular Kripke frames.
Levan Uridia

Language

Functional Analysis of Contrasting Conjunctions in Georgian
Abstract
There exist eight conjunctions in Georgian that are used to express semantic or pragmatic contrast. They can be presented as a hierarchy: aramed > oγond > tumca > magram > k’i//k’idev > xolo > tu > da. The hierarchy is organized in such a way that the ability of conjunctions to express contrasting conjoining decreases from the left to the right. On the basis of functional analysis of the conjunctions, we propose seven binary differential semantic/pragmatic features: +/–[Contrast], +/–[Opposition], +/–[Correction], +/–[Expectation], +/–[Wish], +/–[At least one], +/–[Strong underlining]. Certain combinations of the features express the main functions of the conjunctions which are relevant for formal representations of contrastive topics and/or focuses during the joining of some constituents or sentences.
Rusudan Asatiani
Discourse Relations and Relevance Implicatures: A Case Study
Abstract
In this paper, we discuss dependencies between rhetorical discourse structure and relevance implicatures. We follow [3] and infer relevance implicatures from the assumption that an answer provides optimal information for solving an explicitly or implicitly given decision problem of the inquirer. Such a decision problem can be identified with a question raised in the conversation. Background questions not only depend on explicit questions under discussion but may also be raised by rhetorical relations such as Concession or Contrast. In this paper, we are especially concerned with implicatures of embedded questions. We show by some examples that determining the rhetorical relation that connects two text spans and setting up a pragmatic model that explains the implicatures of embedded sentences interact with each other.
Anton Benz, Fabienne Salfner
Clitic Movement in Pregroup Grammar: A Cross-Linguistic Approach
Abstract
The calculus of pregroups is a kind of type (or categorial) grammar introduced by Lambek [17] for the analysis and computation of natural languages; it has been applied to a wide range of languages from English and German, to French and Italian, and many others [11]. Like Lambek’s Syntactic Calculus, pregroups are non-commutative structures, but the syntax of natural languages shows also the presence of cyclic patterns, in particular those exhibited by the phenomenon known in the literature as movement of clitic pronouns in different languages. In this paper we propose an extension of the calculus of pregroups including two cyclic rules and use them to formally analyze movement of clitic clusters in Persian, French, and Italian. In the final part of the paper, we discuss the relations of these rules to Yetter’s and Abrusci’s cyclic rules for Linear Logic.
Claudia Casadio, Mehrnoosh Sadrzadeh
The Functions of the Particles mxolod and mart’o in Georgian
Abstract
The paper discusses the meaning and functions of the Georgian lexical items mxolod and mart’o. It shows that both are focus particles which can substitute each other in particular contexts and that mxolod,unlike mart’o, can be negated and imply an additive reading. The paper further shows that mart’o can be categorized as an adverb additionally to its categorization as focus particle. As adverb it can function as adverbial or secondary predicate. Whereas mxolod and mart’o as focus particles relate to physical, countable items, mart’o can denote physical and spiritual properties. It follows from the bi-categorial status of mart’o that mart’o is more productive in word formation than mxolod.
Anna Chutkerashvili
Aspectual Shifts With and Without Type Conflict
Abstract
The paper offers a new type of approach to the semantic phenomenon of adverbial aspect shift. It accounts for standard data that resisted a full theoretical explanation so far and deals with some challenging new data, moreover. The paper develops a new type of approach within the framework of finite-state temporal semantics. According to the proposal made here, temporal prepositions are dynamic presuppositions that can aspectually underspecify a situational concept. Furthermore, the new concept of semantic phase is introduced as an instance of the principle of hierarchical abstraction. Aspectual shifts are treated as reflecting context dependence of adverbial modification, either on the level of sentence internal composition or on the level of discourse. The simple shifting algorithm used derives the correct set of possible readings on the basis of lexical semantic input only, and, furthermore, may claim cognitive plausibility.
Sabine Gründer
Preverbs in Megrelian
Abstract
The preverb is one of the main tools used to reflect spatial relations defining direction or location of an action denoted by a verb. The Megrelian preverb system is quite complex. According to their morphological structure, Megrelian preverbs are of two main types: simple and complex. As for their function, they can be used: 1) to show direction (with verbs of motion or movement); 2) to express orientation, indicating whether a motion is oriented either towards or away from the interlocutors; 3) to indicate perfectivity; 4) to add some shade of meaning, i.e. to derive verbs with some new different semantics.
There are 12 simple preverbs in Megrelian. Complex preverbs are formed from the simple ones by adding location particles or some simple preverbs. Sometimes the semantics of a complex preverb is not equal to the mere sum of its components.
Marine Ivanishvili, Ether Soselia
The Syntax/Semantics Interface: Compositionality Issues
Abstract
This paper explores the hypothesis of Direct Compositionality, which is the hypothesis that natural language syntax and semantics work in tandem. The syntax is a system proving expressions well-formed (often proving larger expressions well-formed on the basis of their smaller constituent parts) while the semantics works directly with this to supply a model theoretic interpretation to each expression as it is built in the syntax. The paper considers a few apparent challenges to this hypothesis, and exposits the types of tools which have been used in order to meet these challenges. We begin with some classic results from Montague [1]; turn to extensions of this program that were explored in subsequent work, and end with some recent work of the present author. The goal is to show that many of the apparent challenges can easily be met by simply viewing meanings as slightly more complex packagings than an initial naive view would have it; the tools for accomplishing this themselves are quite simple.
Pauline Jacobson
A Finite State Approach to Abkhaz Morphology and Stress
Abstract
The West Caucasian language Abkhaz is characterized by a rich but rather regular agglutinative morphology. Word stress, however, is free and dynamic and difficult to predict. A theory of stress in Abkhaz has been developed by V. Dybo, A. Spruit and L. Trigo which predicts word stress correctly in the majority of cases. Although stress is not orthographically marked, its position determines the surface representation of Schwa. Thus, in a morphological analyser for the language, stress rules have to be incorporated in order to be able to properly parse and generate orthographic forms. I show how a finite state morphological analyser for Abkhaz can be built that uses the rules developed by Trigo et al.
Paul Meurer
From Inference to Meaning: Experimental Study on Reasoning with Quantifiers Some and Most
Abstract
We report on the results of our reasoning experiments concerning direct inferences with quantifiers: some, most, all. We investigated scalar implicatures of some and most, as well as inferences from all to most, from all to some and from most to some. Based on our results, we propose that scalar implicatures are context-independent and default in this sense that the pragmatic interpretation of the lexical item with which they are connected is preferred in communication. Following Mostowski and Wojtyniak (2004), we observe that meaning of a sentence may be established in two ways: via inference relations in which a sentence stays (inferential meaning) and by investigating how users of the language evaluate the truth-value of the sentence (referential meaning). We treat the pragmatic reading of some and most as their inferential meaning, whereas the logical reading of those quantifiers accounts for the referential meaning. Explaining our results, we attribute the stronger acceptance of inferences from all to most and from most to some when compared to acceptance of inferences from all to some to vagueness of some and most.
Maria Spychalska
The Imperfect Measure of Internally Plural Events
Abstract
This paper discusses event-internal pluractional verbs, i.e. morphologically complex verbs that denote events constituted by pluralities of phases, under the hypothesis that they describe non-canonical events. Non-canonicity is understood in comparative terms with respect to the description of the events provided by the corresponding simplex verb forms; It is modelled via the modification of a measure of the event or of a participant in the event. The diminutive and augmentative types of event-internal pluractionality reported in the literature are made to correspond to the two possible ways in which the measures taken on phases, relatively to different dimensions, are put together to provide the measure of the whole event.
Lucia M. Tovena
The Meaning of the Additive Too: Presupposition and Discourse Similarity
Abstract
This paper studies the general meaning of the additive particle too. It is argued that besides its well-known presuppositional content, too also conveys an information regarding the similarity of its host and the antecedent of its presupposition in the discourse. We couch our proposal in an argumentative framework. This proposal is then articulated with recent accounts of the obligatoriness of too.
Grégoire Winterstein
Bayesian NL Interpretation and Learning
Abstract
Everyday natural language communication is normally successful, even though contemporary computational linguistics has shown that NL is characterised by very high degree of ambiguity and the results of stochastic methods are not good enough to explain the high success rate. Bayesian natural language interpretation and the combination with speaker self-monitoring are proposed as an explanation of the high success rates. The consequences of the model for language learning are briefly explored (inhibitory effects of production in understanding can only emerge when production is good enough, and inhibitory effects of comprehension in production only when comprehension is good enough) and applied to production-comprehension asymmetries.
Henk Zeevat
Backmatter
Metadaten
Titel
Logic, Language, and Computation
herausgegeben von
Nick Bezhanishvili
Sebastian Löbner
Kerstin Schwabe
Luca Spada
Copyright-Jahr
2011
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-22303-7
Print ISBN
978-3-642-22302-0
DOI
https://doi.org/10.1007/978-3-642-22303-7