In this paper, I show that the availability of what some authors have called the weak reading and the strong reading of donkey sentences with relative clauses is systematically related to monotonicity properties of the determiner. The correlation is different from what has been observed in the literature in that it concerns not only right monotonicity, but also left monotonicity (persistence/antipersistence). I claim that the reading selected by a donkey sentence with a double monotone determiner is in fact the one (...) that validates inference based on the left monotonicity of the determiner. This accounts for the lack of strong reading in donkey sentences with MON determiners, which have been neglected in the literature. I consider the relevance of other natural forms of inference as well, but also suggest how monotonicity inference might play a central role in the actual process of interpretation. The formal theory is couched in dynamic predicate logic with generalized quantifiers. (shrink)

Some formal properties of enriched systems of Lambek calculus with analogues of conjunction and disjunction are investigated. In particular, it is proved that the class of languages recognizable by the Lambek calculus with added intersective conjunction properly includes the class of finite intersections of context-free languages.

It is proved that for any k, the class of classical categorial grammars that assign at most k types to each symbol in the alphabet is learnable, in the Gold (1967) sense of identification in the limit from positive data. The proof crucially relies on the fact that the concept known as finite elasticity in the inductive inference literature is preserved under the inverse image of a finite-valued relation. The learning algorithm presented here incorporates Buszkowski and Penn's (1990) algorithm for (...) determining categorial grammars from input consisting of functor-argument structures. (shrink)

Every language recognized by the Lambek calculus with brackets is context-free. This is shown by combining an observation by Jäger with an entirely straightforward adaptation of the method Pentus used for the original Lambek calculus. The case of the variant of the calculus allowing sequents with empty antecedents is slightly more complicated, requiring a restricted use of the multiplicative unit.

I present a new syntactical method for proving the Interpolation Theorem for the implicational fragment of intuitionistic logic and its substructural subsystems. This method, like Prawitz’s, works on natural deductions rather than sequent derivations, and, unlike existing methods, always finds a ‘strongest’ interpolant under a certain restricted but reasonable notion of what counts as an ‘interpolant’.

This volume is an outgrowth of the second Workshop on Logic, Language and Computation held at Stanford in the spring of 1993. The workshop brought together researchers interested in natural language to discuss the current state of the art at the borderline of logic, linguistics and computer science. The papers in this collection fall into three central research areas of the nineties, namely quantifiers, deduction, and context. Each contribution reflects an ever-growing interest in a more dynamic approach to meaning, which (...) focuses on inference patterns and the interpretation of sentences in the context of a larger discourse. The papers apply either current logical machinery - such as linear logic, generalised quantifier theory, dynamic logic - or formal analyses of the notion of context in discourse to classical linguistic issues, with original and thought-provoking results deserving of a wide audience. (shrink)

Second-order abstract categorial grammars (de Groote in Association for computational linguistics, 39th annual meeting and 10th conference of the European chapter, proceedings of the conference, pp. 148–155, 2001) and hyperedge replacement grammars (Bauderon and Courcelle in Math Syst Theory 20:83–127, 1987; Habel and Kreowski in STACS 87: 4th Annual symposium on theoretical aspects of computer science. Lecture notes in computer science, vol 247, Springer, Berlin, pp 207–219, 1987) are two natural ways of generalizing “context-free” grammar formalisms for string and tree (...) languages. It is known that the string generating power of both formalisms is equivalent to (non-erasing) multiple context-free grammars (Seki et al. in Theor Comput Sci 88:191–229, 1991) or linear context-free rewriting systems (Weir in Characterizing mildly context-sensitive grammar formalisms, University of Pennsylvania, 1988). In this paper, we give a simple, direct proof of the fact that second-order ACGs are simulated by hyperedge replacement grammars, which implies that the string and tree generating power of the former is included in that of the latter. The normal form for tree-generating hyperedge replacement grammars given by Engelfriet and Maneth (Graph transformation. Lecture notes in computer science, vol 1764. Springer, Berlin, pp 15–29, 2000) can then be used to show that the tree generating power of second-order ACGs is exactly the same as that of hyperedge replacement grammars. (shrink)

Building on Ben-Avi and Winter’s (2007) work, this paper provides a general “intensionalization” procedure that turns an extensional semantics for a language into an intensionalized one that is capable of accommodating “truly intensional” lexical items without changing the compositional semantic rules. We prove some formal properties of this procedure and clarify its relation to the procedure implicit in Montague’s (1973) PTQ.

Che 1-pu. Han'guk ŭi kaebyŏk -- 1. Kŭndae Han'guk konggongsŏng ŭi chŏn'gae wa t'aja waŭi yŏndae -- 2. Kŭndae Han'guk siminjŏk konggongsŏng ŭi sŏngnip -- 3. Taejonggyo pŏmt'unggusŭjuŭi wa pop'yŏnjuŭi -- Che 2-pu. Ilbon ŭi kaebyŏk -- 1. Kŭnse Ilbon sasang ŭi Sŏngin'gwan -- 2. Ilbon sinjonggyo ŭi kaebyŏk undong -- 3. Hyŏndae Ilbon ŭi saengmyŏng yŏngsŏng kwa ch'iyu yŏngsŏng -- Che 3-pu. Sirhak ŭi sigak -- 1. 19-segi sirhakcha ŭi Ilbon insik -- 2. Ch'oe Han-gi ŭi chonggyo hoet'ong sasang (...) -- 3. Han'guk, Ilbon, Chungguk e issŏsŏ 'Sinsirhangnon' pigyo -- Che 4-pu. Pigyo ŭi sigak -- 1. Ilbon esŏŭi T'oegye, Yulgok, Tasan yŏn'gu ŭi hŭrŭm -- 2. Ch'oe Han-gi wa Ilbon ŭi konggong sasangga pigyo yŏn'gu -- 3. Tongsŏyang konggongsŏng yŏn'gu wa Han'gukchŏk konggongsŏn. (shrink)

没後20年、いま必要な歴史に裏打ちされた予見力、現実政治に提言する率直さ、道義性と理想主義。.

Akama et al. [1] introduced a hierarchical classification of first-order formulas for a hierarchical prenex normal form theorem in semi-classical arithmetic. In this paper, we give a justification for the hierarchical classification in a general context of first-order theories. To this end, we first formalize the standard transformation procedure for prenex normalization. Then we show that the classes $$\textrm{E}_k$$ and $$\textrm{U}_k$$ introduced in [1] are exactly the classes induced by $$\Sigma _k$$ and $$\Pi _k$$ respectively via the transformation procedure in (...) any first-order theory. (shrink)

Akama et al. [1] systematically studied an arithmetical hierarchy of the law of excluded middle and related principles in the context of first-order arithmetic. In that paper, they first provide a prenex normal form theorem as a justification of their semi-classical principles restricted to prenex formulas. However, there are some errors in their proof. In this paper, we provide a simple counterexample of their prenex normal form theorem [1, Theorem 2.7], then modify it in an appropriate way which still serves (...) to largely justify the arithmetical hierarchy. In addition, we characterize a variety of prenex normal form theorems by logical principles in the arithmetical hierarchy. The characterization results reveal that our prenex normal form theorems are optimal. For the characterization results, we establish a new conservation theorem on semi-classical arithmetic. The theorem generalizes a well-known fact that classical arithmetic is $\Pi _2$ -conservative over intuitionistic arithmetic. (shrink)

専門的な予備知識は仮定せずに完全性定理や計算可能性から論じ、第一および第二不完全性定理、Rosserの定理、Hilbertのプログラム、G ̈odelの加速定理、算術の超準モデル、Kolmogorov複雑性などを紹介して、不完全性定理の数学的意義と、その根源にある哲学的問題を説く。.

Within a weak subsystem of second-order arithmetic , that is -conservative over , we reformulate Kreisel's proof of the Second Incompleteness Theorem and Boolos' proof of the First Incompleteness Theorem.

We propose a new game to strategically justify the constrained equal awards rule in claims problems. Our game is “procedurally fair” and “multilateral”. In addition, even if claimants cannot reach an agreement in any period, they can renegotiate in the next period. We show that, for each claims problem, the awards vector chosen by the constrained equal awards rule achieved at period 1 is the unique subgame perfect equilibrium outcome of the game.