While monadic second-order logic (MSO) has played a prominent role in model theoretic syntax, modal logics have been used in this context since its inception. When comparing propositional dynamic logic (PDL) to MSO over trees, Kracht (1997) noted that there are tree languages that can be defined in MSO that can only be defined in PDL by adding new features whose distribution is predictable. He named such features “inessential features”. We show that Kracht’s observation can be extended to other modal (...) logics of trees in two ways. First, we demonstrate that for each stronger logic, there exists a tree language that can only be defined in a weaker logic with inessential features. Second, we show that any tree language that can be defined in a stronger logic, but not in some weaker logic, can be defined with inessential features. Additionally, we consider Kracht’s definition of inessential features more closely. It turns out that there are features whose distribution can be predicted, but who fail to be inessential in Kracht’s sense. We will look at ways to modify his definition. (shrink)

This paper establishes a connection between structure sensitive categorial inference and classical modal logic. The embedding theorems for non-associative Lambek Calculus and the whole class of its weak Sahlqvist extensions demonstrate that various resource sensitive regimes can be modelled within the framework of unimodal temporal logic. On the semantic side, this requires decomposition of the ternary accessibility relation to provide its correlation with standard binary Kripke frames and models.

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.

The aim of the present book is to give a comprehensive account of the ‘state of the art’ of substructural logics, focusing both on their proof theory and on their semantics (both algebraic and relational. It is for graduate students in either philosophy, mathematics, theoretical computer science or theoretical linguistics as well as specialists and researchers.

Geach’s rich paper ‘A Program for Syntax’ introduced many ideas into the arena of categorial grammar, not all of which have been given the attention they warrant in the thirty years since its first publication. Rather surprisingly, one of our findings (Section 3 below) is that the paper not only does not contain a statement of what has widely come to be known as “Geach’s Rule”, but in fact presents considerations which are inimical to the adoption of the rule in (...) question. With regard to at least some amongst the numerous other points extracted here from Geach’s discussion, we shall not be able to reach so definitive a conclusion, and content ourselves with giving the issues an airing. (shrink)

This paper solves a natural but still open question: can abstract categorial grammars (ACGs) respresent usual categorial grammars? Despite their name and their claim to be a unifying framework, up to now there was no faithful representation of usual categorial grammars in ACGs. This paper shows that Non-Associative Lambek grammars as well as their derivations can be defined using ACGs of order two. To conclude, the outcome of such a representation are discussed.

This paper solves a natural but still open question: can abstract categorial grammars respresent usual categorial grammars? Despite their name and their claim to be a unifying framework, up to now there was no faithful representation of usual categorial grammars in ACGs. This paper shows that Non-Associative Lambek grammars as well as their derivations can be defined using ACGs of order two. To conclude, the outcome of such a representation are discussed.

This paper reminds, puts in order, sketches and also initiates some researches from the field of logic and philosophy of language. It lays emphasis on the logical-linguistic and ontological developmental lines originated with Polish researchers. The author discusses two opposite orientations of the former line in the process of formalization of language, called here nominalistic and Platonistic. The paper mentions the author's result (1989; 1991) concerning theoretical equivalence of two axiomatic approaches to language syntax which take into consideration these two (...) different philosophical orientations, respectively. It also introduces certain formal-logical foundations of language semantics, discusses and develops the problem of the syntactic and semantic categorial agreement, i.e. the agreement of the syntactic category of each language expression with the ontological category assigned to the reference of this expression. The author, in particular, gives a solution to this problem for quantifiers. (shrink)

volumes of his work, in his discussions of what underlay a Wissenschaftslehre or theory of science in the sense of his conception; he did so with such purity and scientific strictness, and with such a rich store of original, scientifically confirmed and fruitful thoughts, that we must count him as one of the greatest logicians of all time. He must be placed historically in fairly close proximity to Leibniz, with whom he shares important thoughts and fundamental conceptions, and to whom (...) he is also philosophically akin in other respects.". (shrink)

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. (shrink)

This paper is a reflexion on the computability of natural language semantics. It does not contain a new model or new results in the formal semantics of natural language: it is rather a computational analysis, in the context for type-logical grammars, of the logical models and algorithms currently used in natural language semantics, defined as a function from a grammatical sentence to a set of logical formulas—because a statement can be ambiguous, it can correspond to multiple formulas, one for each (...) reading. We argue that as long as we do not explicitly compute the interpretation in terms of possible world models, one can compute the semantic representation of a given statement, including aspects of lexical meaning. This is a very generic process, so the results are, at least in principle, widely applicable. We also discuss the algorithmic complexity of this process. (shrink)

The Lambek-Grishin calculus is a symmetric version of categorial grammar obtained by augmenting the standard inventory of type-forming operations (product and residual left and right division) with a dual family: coproduct, left and right difference. Interaction between these two families is provided by distributivity laws. These distributivity laws have pleasant invariance properties: stability of interpretations for the Curry-Howard derivational semantics, and structure-preservation at the syntactic end. The move to symmetry thus offers novel ways of reconciling the demands of natural language (...) form and meaning. (shrink)

In this paper we concentrate mainly on the notion of β-pregroups, which are pregroups enriched with modality operators. β-pregroups were first proposed by Fadda [11] in 2001. The motivation to introduce them was to limit 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. 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. (shrink)

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. (shrink)

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(Γ). (shrink)

This paper investigates the learnability by positive examples in the sense of Gold of Pregroup Grammars. In a first part, Pregroup Grammars are presented and a new parsing strategy is proposed. Then, theoretical learnability and non-learnability results for subclasses of Pregroup Grammars are proved. In the last two parts, we focus on learning Pregroup Grammars from a special kind of input called feature-tagged examples. A learning algorithm based on the parsing strategy presented in the first part is given. Its validity (...) is proved and its properties are examplified. (shrink)