On Reduction Systems Equivalent to The Lambek Calculus with the Empty String

The paper continues a series of results on cut-rule axiomatizability of the Lambek calculus. It provides a complete solution of a problem which was solved partially in one of the author's earlier papers. It is proved that the product-free Lambek Calculus with the empty string (L ₀) is not finitely axiomatizable if the only rule of inference admitted is Lambek's cut rule. The proof makes use of the (infinitely) cut-rule axiomatized calculus C designed by the author exactly for this purpose.     

The Pentus Theorem for Lambek Calculus with Simple Nonlogical Axioms

The Lambek calculus introduced in Lambek [6] is a strengthening of the type reduction calculus of Ajdukiewicz [1]. We study Associative Lambek Calculus L in Gentzen style axiomatization enriched with a finite set Γ of nonlogical axioms, denoted by L(Γ).It is known that finite axiomatic extensions of Associative Lambek Calculus generate all recursively enumerable languages (see Buszkowski [2]). Then we confine nonlogical axioms to sequents of the form p → q, where p and q are atomic types. For calculus L(Γ) we prove interpolation lemma (modifying the Roorda proof for L [10]) and the binary reduction lemma (using the Pentus method [9] with modification from [3]). In consequence we obtain the weak equivalence of the Context-Free Grammars and grammars based on L(Γ).     

The finite model property for BCI and related systems

We prove the finite model property (fmp) for BCI and BCI with additive conjunction, which answers some open questions in Meyer and Ono [11]. We also obtain similar results for some restricted versions of these systems in the style of the Lambek calculus [10, 3]. The key tool is the method of barriers which was earlier introduced by the author to prove fmp for the product-free Lambek calculus [2] and the commutative product-free Lambek calculus [4].Presented by H. Ono     

A direct proof of the equivalence of free categorial grammars and simple phrase structure grammars

In [2], Bar-Hillel, Gaifman, and Shamir prove that the simple phrase structure grammars (SPGs) defined by Chomsky are equivalent in a certain sense to Bar-Hillel's bidirectional categorial grammars (BCGs). On the other hand, Cohen [3] proves the equivalence of the latter ones to what the calls free categorial grammars (FCGs). They are closely related to Lambek's syntactic calculus which, in turn, is based on the idea due to Ajdukiewicz [1]. For the reasons which will be discussed in the last section, Cohen's proof seems to be at least incomplete. This paper yields a direct proof of the equivalence ofFCGs andSPGs.Allatum est die S Marlii 1976     

On the Complexity of Nonassociative Lambek Calculus with Unit

Nonassociative Lambek Calculus (NL) is a syntactic calculus of types introduced by Lambek [8]. The polynomial time decidability of NL was established by de Groote and Lamarche [4]. Buszkowski [3] showed that systems of NL with finitely many assumptions are decidable in polynomial time and generate context-free languages; actually the P-TIME complexity is established for the consequence relation of NL. Adapting the method of Buszkowski [3] we prove an analogous result for Nonassociative Lambek Calculus with unit (NL1). Moreover, we show that any Lambek grammar based on NL1 (with assumptions) can be transformed into an equivalent context-free grammar in polynomial time.     

P-Compatible Hypersubstitution and MP-Solid Varieties

The study of hyperidentities is a growing field of research. While hyperidentities hark back to before 1965 (cf. [1]), they have found a rebirth in the late seventies and early eighties (cf. [8], [9]). It is being expanded in several directions, from connections with clone theory, to finite basis problems, to semigroup theory, to classification of M-solid varieties. Applications to digital logic, formal languages, and hypertext systems have been suggested. The concept of a P-compatible equation, where P is a partition on the set of operation symbols, is a good tool to study the structure of identities. In [4] we asked for P-compatible hyperidentities. In this paper we will consider hypersubstitutions which are compatible with the partition P and will develop a generalized equational theory for certain P-compatible hyperidentities. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the Logic of β-pregroups

In this paper we concentrate mainly on the notion of β-pregroups, which are pregroups (first introduced by Lambek [18] in 1999) enriched with modality operators. β-pregroups were first proposed by Fadda [11] in 2001. The motivation to introduce them was to limit (locally) the associativity in the calculus considered. In this paper we present this new calculus in the form of a rewriting system, prove the very important feature of this system - that in a given derivation the non-expanding rules must always proceed non-contracting ones in order the derivation to be minimal (normalization theorem). We also propose a sequent system for this calculus and prove the cut elimination theorem for it. As an illustration we show how to use β-pregroups for linguistical applications. Special Issue Categorial Grammars and Pregroups Edited by Wojciech Buszkowski and Anne Preller     

Distributive Full Lambek Calculus Has the Finite Model Property

We prove the Finite Model Property (FMP) for Distributive Full Lambek Calculus (DFL) whose algebraic semantics is the class of distributive residuated lattices (DRL). The problem was left open in [8, 5]. We use the method of nuclei and quasi–embedding in the style of [10, 1]. Presented by Daniele Mundici.     

Proof Nets for the Multimodal Lambek Calculus

We present a novel way of using proof nets for the multimodal Lambek calculus, which provides a general treatment of both the unary and binary connectives. We also introduce a correctness criterion which is valid for a large class of structural rules and prove basic soundness, completeness and cut elimination results. Finally, we will present a correctness criterion for the original Lambek calculus Las an instance of our general correctness criterion.     

A Rule-Extension of the Non-Associative Lambek Calculus

An extension L ⁺ of the non-associative Lambek calculus Lis defined. In L ⁺ the restriction to formula-conclusion sequents is given up, and additional left introduction rules for the directional implications are introduced. The system L ⁺ is sound and complete with respect to a modification of the ternary frame semantics for L.     

Infinitary Action Logic: Complexity, Models and Grammars

Action logic of Pratt [21] can be presented as Full Lambek Calculus FL [14, 17] enriched with Kleene star *; it is equivalent to the equational theory of residuated Kleene algebras (lattices). Some results on axiom systems, complexity and models of this logic were obtained in [4, 3, 18]. Here we prove a stronger form of *-elimination for the logic of *-continuous action lattices and the –completeness of the equational theories of action lattices of subsets of a finite monoid and action lattices of binary relations on a finite universe. We also discuss possible applications in linguistics. Presented by Jacek Malinowski     

Type Logics and Pregroups

We discuss the logic of pregroups, introduced by Lambek [34], and its connections with other type logics and formal grammars. The paper contains some new ideas and results: the cut-elimination theorem and a normalization theorem for an extended system of this logic, its P-TIME decidability, its interpretation in L1, and a general construction of (preordered) bilinear algebras and pregroups whose universe is an arbitrary monoid. Special Issue Categorial Grammars and Pregroups Edited by Wojciech Buszkowski and Anne Preller     

Axiomatization and completeness of uncountably valued approximation logic

A first order uncountably valued logicL _Q(0,1) for management of uncertainty is considered. It is obtained from approximation logicsL _T of any poset type (T, ) (see Rasiowa [17], [18], [19]) by assuming (T, )=(Q(0, 1), ) — whereQ(0, 1) is the set of all rational numbersq such that 0<q<1 and is the arithmetic ordering — by eliminating modal connectives and adopting a semantics based onLT-fuzzy sets (see Rasiowa and Cat Ho [20], [21]). LogicL _Q(0,1) can be treated as an important case ofLT-fuzzy logics (introduced in Rasiowa and Cat Ho [21]) for (T, )=(Q(0, 1), ), i.e. asLQ(0, 1)-fuzzy logic announced in [21] but first examined in this paper.L _Q(0,1) deals with vague concepts represented by predicate formulas and applies approximate truth-values being certain subsets ofQ(0, 1). The set of all approximate truth-values consists of the empty set ø and all non-empty subsetss ofQ(0, 1) such that ifqs andqq, thenqs. The setLQ(0, 1) of all approximate truth-values is uncountable and covers up to monomorphism the closed interval [0, 1] of the real line.LQ(0, 1) is a complete set lattice and therefore a pseudo-Boolean (Heyting) algebra. Equipped with some additional operations it is a basic plain semi-Post algebra of typeQ(0, 1) (see Rasiowa and Cat Ho [20]) and is taken as a truth-table forL _Q(0,1) logic.L _Q(0,1) can be considered as a modification of Zadeh's fuzzy logic (see Bellman and Zadeh [2] and Zadeh and Kacprzyk, eds. [29]). The aim of this paper is an axiomatization of logicL _Q(0,1) and proofs of the completeness theorem and of the theorem on the existence ofLQ(0, 1)-models (i.e. models under the semantics introduced) for consistent theories based on any denumerable set of specific axioms. Proofs apply the theory of plain semi-Post algebras investigated in Cat Ho and Rasiowa [4].Presented byCecylia Rauszer     

面向汉语认知与功能特征的语法逻辑

本文研究范畴语法的两种扩充,一是从认知特征角度的扩充,将范畴语法扩充为认知特征范畴语法,通过具有完全性的逻辑证明解决了一些不合语言事实的句子判别问题;二是从功能特征角度的扩充,提出逻辑推理的形式和进一步将二者统一的可能性问题。     

Tableaux for Łukasiewicz Infinite-valued Logic

In this work we propose a labelled tableau method for ukasiewicz infinite-valued logic L . The method is based on the Kripke semantics of this logic developed by Urquhart [25] and Scott [24]. On the one hand, our method falls under the general paradigm of labelled deduction [8] and it is rather close to the tableau systems for sub-structural logics proposed in [4]. On the other hand, it provides a CoNP decision procedure for L validity by reducing the check of branch closure to linear programming     

A study of intermediate propositional logics on the third slice

The intermediate logics have been classified into slices (cf. Hosoi [1]), but the detailed structure of slices has been studied only for the first two slices (cf. Hosoi and Ono [2]). In order to study the structure of slices, we give a method of a finer classification of slices & _n (n 3). Here we treat only the third slice as an example, but the method can be extended to other slices in an obvious way. It is proved that each subslice contains continuum of logics. A characterization of logics in each subslice is given in terms of the form of models.     

Book notes

There is a standard objection against purported explanations of how a language L can express the notion of being a true sentence of L. According to this objection, such explanations avoid one paradox (the Liar) only to succumb to another of the same kind. Even if L can contain its own truth predicate, we can identify another notion it cannot express, on pain of contradiction via Liar-like reasoning. This paper seeks to undermine such ‘revenge’ by arguing that it presupposes a dubious assumption about the linguistic expression of concepts. Successful revenge would require that there be a notion other than truth that plays the same role with respect to concept-expression that truth is naturally thought to play before we are confronted with the Liar paradox.

La vendetta, oh, la vendetta?Revenge, oh revenge

è un piacer serbato ai saggi.?is a pleasure reserved for the wise.

[…] il fatto è serio …?[…] the case is serious …

ma credete si farà.?but trust me, I'll take care of it.

Se tutto il codice dovessi volgere,?If I have to turn over the whole law-book,

se tutto l'indice dovessi leggere,?if I have to read through the whole index,

con un equivoco, con un sinonimo?with an equivocation, with a synonym

qualche garbuglio si troverà.?I'll find some way to tangle things up.

[…] il birbo Figaro vinto sarà.?[…] that rascal Figaro will be defeated.

Dr Bartolo, from da Ponte's libretto to Mozart's The Marriage of Figaro     

Relevant Robinson's arithmetic

In this paper two different formulations of Robinson's arithmetic based on relevant logic are examined. The formulation based on the natural numbers (including zero) is shown to collapse into classical Robinson's arithmetic, whereas the one based on the positive integers (excluding zero) is shown not to similarly collapse. Relations of these two formulations to R. K. Meyer's system R# of relevant Peano arithmetic are examined, and some remarks are made about the role of constant functions (e.g., multiplication by zero) in relevant arithmetic.This paper has been greatly influenced by the (largely unpublished) work of E. K. Meyer (cf. [7]) on relevant arithmetic, and I wish to thank him, and also N. D. Belnap, Jr. and D. Cohen for helpful advice. In fairness to Meyer it must be said that he finds my axioms 13 and 13(1) too strong (they are not theorems of his system R# - cf. §4 below). Meyer tells me be finds vindication for his view in my chief theorem of §2. For myself, I find the insights behind Meyer's work on R# to be both stable and fruitful, and if I now had to make a choice, I would follow Meyer in his rejection of my axioms. However, the systems I explore in this paper themselves have a surprising amount of internal consistency of motivation (cf. §5). Let a hundred formal systems bloom.     

Intermediate logics with the same disjunctionless fragment as intuitionistic logic

Given an intermediate prepositional logic L, denote by L ^–d its disjuctionless fragment. We introduce an infinite sequence {J _n}_n1 of propositional formulas, and prove:(1)For any L: L ^–d =I ^–d (I=intuitionistic logic) if and only if J _n L for every n 1.Since it turns out that L{J _{n} n}1 = Ø for any L having the disjunction property, we obtain as a corollary that L ^–d = I ^–d for every L with d.p. (cf. open problem 7.19 of [5]). Algebraic semantic is used in the proof of the if part of (1). In the last section of the paper we provide a characterization in Kripke's semantic for the logics J _n =I+ +J _n (n 1).     

Maximal weakly-intuitionistic logics

This article introduces the three-valuedweakly-intuitionistic logicI ¹ as a counterpart of theparaconsistent calculusP ¹ studied in [11].I ¹ is shown to be complete with respect to certainthree-valued matrices. We also show that in the sense that any proper extension ofI ¹ collapses to classical logic.The second part shows thatI ¹ is algebraizable in the sense of Block and Pigozzi (cf. [2]) in a way very similar to the algebraization ofP ¹ given in [8].In the last part of the paper we suggest the definition of certain hierarchies of finite-valued propositional paraconsistent and weakly-intuitionistic calculi, and comment on their intrinsic interest.