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.     

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     

A simple and general method of solving the finite axiomatizability problems for Lambek's syntactic calculi

In [4], I proved that the product-free fragment L of Lambek's syntactic calculus (cf. Lambek [2]) is not finitely axiomatizable if the only rule of inference admitted is Lambek's cut-rule. The proof (which is rather complicated and roundabout) was subsequently adapted by Kandulski [1] to the non-associative variant NL of L (cf. Lambek [3]). It turns out, however, that there exists an extremely simple method of non-finite-axiomatizability proofs which works uniformly for different subsystems of L (in particular, for NL). We present it below to the use of those who refer to the results of [1] and [4].     

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 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     

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     

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.     

On Varieties of Biresiduation Algebras

A biresiduation algebra is a 〈/,\,1〉-subreduct of an integral residuated lattice. These algebras arise as algebraic models of the implicational fragment of the Full Lambek Calculus with weakening. We axiomatize the quasi-variety B of biresiduation algebras using a construction for integral residuated lattices. We define a filter of a biresiduation algebra and show that the lattice of filters is isomorphic to the lattice of B-congruences and that these lattices are distributive. We give a finite basis of terms for generating filters and use this to characterize the subvarieties of B with EDPC and also the discriminator varieties. A variety generated by a finite biresiduation algebra is shown to be a subvariety of B. The lattice of subvarieties of B is investigated; we show that there are precisely three finitely generated covers of the atom. Mathematics Subject Classification (2000): 03G25, 06F35, 06B10, 06B20 Dedicated to the memory of Willem Johannes Blok     

On Finite Models of the Lambek Calculus

We study a class of finite models for the Lambek Calculus with additive conjunction and with and without empty antecedents. The class of models enables us to prove the finite model property for each of the above systems, and for some axiomatic extensions of them. This work strengthens the results of [3] where only product-free fragments of these systems are considered. A characteristic feature of this approach is that we do not rely on cut elimination in opposition to e.g. [5], [9].     

Completeness of Certain Bimodal Logics for Subset Spaces

Subset Spaces were introduced by L. Moss and R. Parikh in [8]. These spaces model the reasoning about knowledge of changing states.In [2] a kind of subset space called intersection space was considered and the question about the existence of a set of axioms that is complete for the logic of intersection spaces was addressed. In [9] the first author introduced the class of directed spaces and proved that any set of axioms for directed frames also characterizes intersection spaces.We give here a complete axiomatization for directed spaces. We also show that it is not possible to reduce this set of axioms to a finite set.     

Conjunctions,Disjunctions and Lewisian Semantics for Counterfactuals

Consider the reasonable axioms of subjunctive conditionals (1) if p q ₁ and p q ₂ at some world, then p (q ₁ & q ₂) at that world, and (2) if p ₁ q and p ₂ q at some world, then (p ₁ ∨ p ₂) q at that world, where p q is the subjunctive conditional. I show that a Lewis-style semantics for subjunctive conditionals satisfies these axioms if and only if one makes a certain technical assumption about the closeness relation, an assumption that is probably false. I will then show how Lewisian semantics can be modified so as to assure (1) and (2) even when the technical assumption fails, and in fact in one sense the semantics actually becomes simpler then.     

König's Infinity Lemma and Beth's Tree Theorem

König, D. [1926. ‘Sur les correspondances multivoques des ensembles’, Fundamenta Mathematica, 8, 114–34] includes a result subsequently called König's Infinity Lemma. Konig, D. [1927. ‘Über eine Schlussweise aus dem Endlichen ins Unendliche’, Acta Litterarum ac Scientiarum, Szeged, 3, 121–30] includes a graph theoretic formulation: an infinite, locally finite and connected (undirected) graph includes an infinite path. Contemporary applications of the infinity lemma in logic frequently refer to a consequence of the infinity lemma: an infinite, locally finite (undirected) tree with a root has a infinite branch. This tree lemma can be traced to [Beth, E. W. 1955. ‘Semantic entailment and formal derivability’, Mededelingen der Kon. Ned. Akad. v. Wet., new series 18, 13, 309–42]. It is argued that Beth independently discovered the tree lemma in the early 1950s and that it was later recognized among logicians that Beth's result was a consequence of the infinity lemma. The equivalence of these lemmas is an easy consequence of a well known result in graph theory: every connected, locally finite graph has among its partial subgraphs a spanning tree.     

The Simplest Axiom System for Plane Hyperbolic Geometry Revisited

Using the axiom system provided by Carsten Augat in [1], it is shown that the only 6-variable statement among the axioms of the axiom system for plane hyperbolic geometry (in Tarski’s language L _B≡), we had provided in [3], is superfluous. The resulting axiom system is the simplest possible one, in the sense that each axiom is a statement in prenex form about at most 5 points, and there is no axiom system consisting entirely of at most 4-variable statements.     

The Concurrent,Continuous Fluent Calculus

The Fluent Calculus belongs to the established predicate calculus formalisms for reasoning about actions. Its underlying concept of state update axioms provides a solution to the basic representational and inferential Frame Problems in pure first-order logic. Extending a recent research result, we present a Fluent Calculus to reason about domains involving continuous change and where actions occur concurrently.     

Proving theorems of the second order Lambek calculus in polynomial time

In the Lambek calculus of order 2 we allow only sequents in which the depth of nesting of implications is limited to 2. We prove that the decision problem of provability in the calculus can be solved in time polynomial in the length of the sequent. A normal form for proofs of second order sequents is defined. It is shown that for every proof there is a normal form proof with the same axioms. With this normal form we can give an algorithm that decides provability of sequents in polynomial time.The author was sponsored by project NF 102/62–356 (Structural and Semantic Parallels in Natural Languages and Programming Languages), funded by the Netherlands Organization for the Advancement of Research (NWO).Presented byCecylia Rauszer     

Second order propositional operators over cantor space

We consider propositional operators defined by propositional quantification in intuitionistic logic. More specifically, we investigate the propositional operators of the formA* :p q(p A(q)) whereA(q) is one of the following formulae: (¬¬q q) V ¬¬q, (¬¬q q) (¬¬q V ¬q), ((¬¬q q) (¬¬q V ¬q)) ((¬¬q q) V ¬¬q). The equivalence ofA*(p) to ¬¬p is proved over the standard topological interpretation of intuitionistic second order propositional logic over Cantor space.We relate topological interpretations of second order intuitionistic propositional logic over Cantor space with the interpretation of propositional quantifiers (as the strongest and weakest interpolant in Heyting calculus) suggested by A. Pitts. One of the merits of Pitts' interpretation is shown to be valid for the interpretation over Cantor space.Presented byJan Zygmunt     

Nontransitive measurable utility

A new theory of preferences under risk is presented that does not use the transitivity and independence axioms of the von Neumann-Morgenstern linear utility theory. Utilities in the new theory are unique up to a similarity transformation (ratio scale measurement). They key to this generalization of the traditional linear theory lies in its representation of binary preferences by a bivariate rather than univariate real valued function. Linear theory obtains a linear function u on a set P of probability measures for which u(p) > u(q) if and only if p is preferred to q. The new theory obtains a skew-symmetric bilinear function φ on P × P for which φ(p, q) > 0 if and only if p is preferred to q. Continuity, dominance, and symmetry axioms are shown to be necessary and sufficient for the new representation.     

Reasons and Entailment

What is the relation between entailment and reasons for belief? In this paper, I discuss several answers to this question, and I argue that these answers all face problems. I then propose the following answer: for all propositions p ₁,…,p _n and q, if the conjunction of p ₁,…, and p _n entails q, then there is a reason against a person’s both believing that p ₁,…, and that p _n and believing the negation of q. I argue that this answer avoids the problems that the other answers to this question face, and that it does not face any other problems either. I end by showing what the relation between deductive logic, reasons for belief and reasoning is if this answer is correct.     

Making the Quantum of Relevance

Summary  The two Heisenberg Uncertainties (UR) entail an incompatibility between the two pairs of conjugated variables E, t and p, q. But incompatibility comes in two kinds, exclusive of one another. There is incompatibility defineable as: (p → − q) & (q→ − p) or defineable as [(p →− q) & (q →− p)] ↔ r. The former kind is unconditional, the latter conditional. The former, in accordance, is fact independent, and thus a matter of logic, the latter fact dependent, and thus a matter of fact. The two types are therefore diametrically opposed.In spite of this, however, the existing derivations of the Uncertainties are shown here to entail both types of incompatibility simultaneously. Δ E Δ t ≥ h is known to derive from the quantum relation E = hν plus the Fourier relation Δ ν Δ t ≥ 1. And the Fourier relation assigns a logical incompatibility between Δ ν = 0, Δ t = 0. (Defining a repetitive phenomenon at an instant t → 0 is a self contradictory notion.) An incompatibility, therefore, which is fact independent and unconditional. How can one reconcile this with the fact that Δ EΔ t exists if and only if h > 0, which latter supposition is a factual truth, entailing that a Δ E = 0, Δ t = 0 incompatibility should itself be fact dependent? Are we to say that E and t are unconditionally incompatible (via Δ ν Δ t ≥ 1) on condition that E = hν is at all true? Hence, as presently standing, the UR express a self-contradicting type of incompatibility.To circumvent this undesirable result, I reinterpret E = hν as relating the energy with a period. Though only one such period. And not with frequency literally. (It is false that E = ν . It is true that E = ν times the quantum.) In this way, the literal concept of frequency does not enter as before, rendering Δ ν Δ t ≥ 1 inapplicable. So the above noted contradiction disappears. Nevertheless, the Uncertainties are derived. If energy is only to be defined over a period, momentum only over a distance (formerly a wavelength) resulting during such period, thus yielding quantized action of dimensions Et = pq, then energies will become indefinite at instants, momenta indefinite at points, leading, as demanded, to (symmetric!) Δ E Δ t = Δ p Δ q ≥ h’s.