Categorial grammar is well-known for its elegant analysis of coordination enabled by the flexible notion of constituency it entertains. However, to date, no systematic study exists that examines whether this analysis has any obvious empirical advantage over alternative analyses of nonconstituent coordination available in phrase structure-based theories of syntax. This paper attempts precisely such a comparison. We compare the direct constituent coordination analysis of non-canonical coordinations in categorial grammar with an ellipsis-based analysis of the same phenomena in the recent HPSG (...) literature. We provide a set of empirical evidence, consisting of cases in which non-canonical coordinations interact with scopal operators of various sorts, which systematically falsifies the predictions of the latter, ‘linearization-based’ ellipsis approach to coordination. We propose an alternative analysis in a variant of categorial grammar called Hybrid Type-Logical Categorial Grammar. The proposed framework builds on both the Lambek-inspired variants of categorial grammar and a more recent line of work modelling word order via a lambda calculus for the prosodic component. The flexible syntax–semantics interface of this framework straightforwardly captures the interactions between non-canonical coordinations and scopal expressions, demonstrating the broader empirical payoff of the direct constituent coordination analysis of non-canonical coordinations pioneered by Steedman :523–568, 1985; Linguist Philos 13:207–263, 1990) and Dowty hitherto not explicitly recognized in the literature. (shrink)

This article presents modal versions of resource-conscious logics. We concentrate on extensions of variants of linear logic with one minimal non-normal modality. In earlier work, where we investigated agency in multi-agent systems, we have shown that the results scale up to logics with multiple non-minimal modalities. Here, we start with the language of propositional intuitionistic linear logic without the additive disjunction, to which we add a modality. We provide an interpretation of this language on a class of Kripke resource models (...) extended with a neighbourhood function: modal Kripke resource models. We propose a Hilbert-style axiomatisation and a Gentzen-style sequent calculus. We show that the proof theories are sound and complete with respect to the class of modal Kripke resource models. We show that the sequent calculus admits cut elimination and that proof-search is in PSPACE. We then show how to extend the results when non-commutative connectives are added to the language. Finally, we put the l.. (shrink)

The paper concentrates on the problem of adequate reflection of fragments of reality via expressions of language and inter-subjective knowledge about these fragments, called here, in brief, language adequacy. This problem is formulated in several aspects, the most being: the compatibility of language syntax with its bi-level semantics: intensional and extensional. In this paper, various aspects of language adequacy find their logical explication on the ground of the formal-logical theory T of any categorial language L generated by the so-called classical (...) categorial grammar, and also on the ground of its extension to the bi-level, intensional and extensional semantic-pragmatic theory ST for L. In T, according to the token-type distinction of Ch.S. Peirce, L is characterized first as a language of well-formed expression-tokens (wfe-tokens) - material, concrete objects - and then as a language of wfe-types - abstract objects, classes of wfe-tokens. In ST the semantic-pragmatic notions of meaning and interpretation for wfe-types of L of intensional semantics and the notion of denotation of extensional semanics for wfe-types and constituents of knowledge are formalized. These notions allow formulating a postulate (an axiom of categorial adequacy) from which follow all the most important conditions of the language adequacy, including the above, and a structural one connected with three principles of compositionality. (shrink)

We consider language models for the Lambek calculus that allow empty antecedents and enrich them with constants for the empty language and for the language containing only the empty word. No complete calculi are known with respect to these semantics, and in this paper we consider several trivalent systems that arise as fragments of these models? logics.

A hyperintensional semantics for natural language is proposed which is agnostic about the question of whether propositions are sets of worlds or worlds are sets of propositions. Montague’s theory of intensional senses is replaced by a weaker theory, written in standard classical higher-order logic, of fine-grained senses which are in a many-to-one correspondence with intensions; Montague’s theory can then be recovered from the proposed theory by identifying the type of propositions with the type of sets of worlds and adding an (...) axiom to the effect that each world is the set of propositions which are true there. Senses are compositionally assigned to linguistic expressions by a categorial grammar with only two rule schemas, based on the implicative fragment of intuitionistic linear propositional logic, and a fully explicit grammar fragment is provided that illustrates the compositional assignment of sense to a variety of constructions, including dummy-subject constructions, infinitive complements, predicative adjectives and nominals, raising to subject, ‘tough-movement’, and quantifier scope ambiguities. Notably, the grammar and the derivations that it licenses never make reference to either worlds or to the extensions of senses. (shrink)

This paper argues for the hypothesis of direct compositionality (as in, e.g., Montague 1974), according to which the combinatory syntactic rules specify a set of well-formed expressions while the semantic combinatory rules work in tandem to directly supply a model-theoretic interpretation to each expression as it is "built" in the syntax. (This thus obviates the need for any level like LF and, concomitantly, for any rules mapping surface structures to such a level.) I focus here on one related group of (...) phenomena: the interaction of "paycheck" pronouns with Weak Crossover effects and i-within-i effects. These interactions were studied in Jacobson (1977) as they show up in Back-Peters sentences. There I argued that these interactions show that paycheck pronouns have a complex representation at LF; here I show that all of the observations in this earlier work are compatible with the hypothesis of direct compositionality. The key tool is the adoption of a variation-free semantics (a semantics which makes no use of variables as part of the semantic machinery). In addition to the general consequences for the syntax/semantics interface, there are two other main results. First, I provide new arguments for a variable-free semantics. For example, it will be shown that under this view the paycheck reading of a pronoun comes for free; most other theories posit additional mechanisms and/or an additional lexical meaning for pronouns, and thus paycheck and regular pronouns are only accidentally homophonous. Second, I reiterate one of the central points in Jacobson (1977): this is that the first pronoun in a Bach-Peters sentence is indeed a paycheck pronoun, and hence nothing special needs to be said about these sentences nor does any new machinery need to be invoked for them. (shrink)

If all dependent expressions were adjacent some variety of immediate constituent analysis would suffice for grammar, but syntactic and semantic mismatches are characteristic of natural language; indeed this is a, or the, central problem in grammar. Logical categorial grammar reduces grammar to logic: an expression is well-formed if and only if an associated sequent is a theorem of a categorial logic. The paradigmatic categorial logic is the Lambek calculus, but being a logic of concatenation the Lambek calculus can only capture (...) discontinuous dependencies when they are peripheral. In this paper we present the displacement calculus, which is a logic of intercalation as well as concatenation and which subsumes the Lambek calculus. On the empirical side, we apply the new calculus to discontinuous idioms, quantification, VP ellipsis, medial extraction, pied-piping, appositive relativisation, parentheticals, gapping, comparative subdeletion, cross-serial dependencies, reflexivization, anaphora, dative alternation, and particle shift. On the technical side, we prove that the calculus enjoys Cut-elimination. (shrink)

Abstract -/- Quantifier domain restriction (QDR) and two versions of nominal restriction (NR) are implemented as restrictions that depend on a previously introduced interpreter and interpretation time in a two-dimensional semantic framework on the basis of simple type theory and categorial grammar. Against Stanley (2002) it is argued that a suitable version of QDR can deal with superlatives like tallest. However, it is shown that NR is needed to account for utterances when the speaker intends to convey different restrictions for (...) multiple uses of the same quantifying determiner. We argue that NR generally fares better with such examples but also observe that examples like Every sailor waves at every sailor might be pragmatically anomalous. An account of contextual domain restriction is proposed that (i) excludes these anomalous readings (but it is shown how they could be included), (ii) makes it possible to express different contextual domain restrictions as long-range dependencies on an interpreter and an interpretation time, and (iii) additionally models restrictions based on locative constructions as general mereological constraints introduced by shifting the index. (shrink)

We show that vector space semantics and functional semantics in two-sorted first order logic are equivalent for pregroup grammars. We present an algorithm that translates functional expressions to vector expressions and vice-versa. The semantics is compositional, variable free and invariant under change of order or multiplicity. It includes the semantic vector models of Information Retrieval Systems and has an interior logic admitting a comprehension schema. A sentence is true in the interior logic if and only if the ‘usual’ first order (...) formula translating the sentence holds. The examples include negation, universal quantifiers and relative pronouns. (shrink)

Current theories of grammar handle both extraction and anaphorization by introducing variables into syntactic representations. Combinatory categorial grammar eliminates variables corresponding to gaps. Using the combinator W, the paper extends this approach to anaphors, which appear to act as overt bound variables. [Slightly extended version in Bartsch et al 1989.].

This paper argues for the idea that in describing language we should follow Haskell Curry in distinguishing between the structure of an expression and its appearance or manifestation . It is explained how making this distinction obviates the need for directed types in type-theoretic grammars and a simple grammatical formalism is sketched in which representations at all levels are lambda terms. The lambda term representing the abstract structure of an expression is homomorphically translated to a lambda term representing its manifestation, (...) but also to a lambda term representing its semantics. (shrink)

This paper introduces λ-grammar, a form of categorial grammar that has much in common with LFG. Like other forms of categorial grammar, λ-grammars are multi-dimensional and their components are combined in a strictly parallel fashion. Grammatical representations are combined with the help of linear combinators, closed pure λ-terms in which each abstractor binds exactly one variable. Mathematically this is equivalent to employing linear logic, in use in LFG for semantic composition, but the method seems more practicable.

This paper uses classical logic for a simultaneous description of the syntax and semantics of a fragment of English and it is argued that such an approach to natural language allows procedural aspects of linguistic theory to get a purely declarative formulation. In particular, it will be shown how certain construction rules in Discourse Representation Theory, such as the rule that indefinites create new discourse referents and definites pick up an existing referent, can be formulated declaratively if logic is used (...) as a metalanguage for English. In this case the declarative aspects of a rule are highlighted when we focus on the model theory of the description language while a procedural perspective is obtained when its proof theory is concentrated on. Themes of interest are Discourse Representation Theory, resolution of anaphora, resolution of presuppositions, and underspecification. (shrink)

This paper uses a partially ordered set of syntactic categories to accommodate optionality and licensing in natural language syntax. A complex but well-studied data set pertaining to the syntax of quantifier scope and negative polarity licensing in Hungarian is used to illustrate the proposal. The presentation is geared towards both linguists and logicians. The paper highlights that the main ideas can be implemented in different grammar formalisms, and discusses in detail an implementation where the partial ordering on categories is given (...) by the derivability relation of a calculus with residuated and Galois-connected unary operators. (shrink)

The ‘syntax’ and ‘combinatorics’ of my title are what Curry (1961) referred to as phenogrammatics and tectogrammatics respectively. Tectogrammatics is concerned with the abstract combinatorial structure of the grammar and directly informs semantics, while phenogrammatics deals with concrete operations on syntactic data structures such as trees or strings. In a series of previous papers (Muskens, 2001a; Muskens, 2001b; Muskens, 2003) I have argued for an architecture of the grammar in which finite sequences of lambda terms are the basic data structures, (...) pairs of terms syntax, semantics for example. These sequences then combine with the help of simple generalizations of the usual abstraction and application operations. This theory, which I call Lambda Grammars and which is closely related to the independently formulated theory of Abstract Categorial Grammars (de Groote, 2001; de Groote, 2002), in fact is an implementation of Curry’s ideas: the level of tectogrammar is encoded by the sequences of lambda-terms and their ways of combination, while the syntactic terms in those sequences constitute the phenogrammatical level. In de Groote’s formulation of the theory, tectogrammar is the level of abstract terms, while phenogrammar is the level of object terms. (shrink)

Substructural logics are logics obtained from a sequent formulation of intuitionistic or classical logic by rejecting some structural rules. The substructural logics considered here are linear logic, relevant logic and BCK logic. It is proved that first-order variants of these logics with an intuitionistic negation can be embedded by modal translations into S4-type extensions of these logics with a classical, involutive, negation. Related embeddings via translations like the double-negation translation are also considered. Embeddings into analogues of S4 are obtained with (...) the help of cut elimination for sequent formulations of our substructural logics and their modal extensions. These results are proved for systems with equality too. (shrink)

We study mathematical and algorithmic properties of Lambek's pregroups and illustrate them by the French noun phrase. An algorithm of complexity n3 to solve the reduction problem in an arbitrary free pregroup as well as recognition by a pregroup grammar is presented. This algorithm is then specified to run in linear time. A sufficient condition for a language fragment that makes the linear algorithm complete is given.

The relationship between Lexical-Functional Grammar (LFG) functional structures (f-structures) for sentences and their semanticinterpretations can be formalized in linear logic in a way thatcorrectly explains the observed interactions between quantifier scopeambiguity, bound anaphora and intensionality.Our linear-logic formalization of the compositional properties ofquantifying expressions in natural language obviates the need forspecial mechanisms, such as Cooper storage, in representing thescoping possibilities of quantifying expressions. Instead, thesemantic contribution of a quantifier is recorded as a linear-logicformula whose use in a proof will establish the (...) scope of thequantifier. Different proofs can lead to different scopes. In eachcomplete proof, the properties of linear logic ensure thatquantifiers are properly scoped. (shrink)

Using the programming-language concept of continuations, we propose a new, multimodal analysis of quantification in Type Logical Grammar. Our approach provides a geometric view of in-situ quantification in terms of graphs, and motivates the limited use of empty antecedents in derivations. Just as continuations are the tool of choice for reasoning about evaluation order and side effects in programming languages, our system provides a principled, type-logical way to model evaluation order and side effects in natural language. We illustrate with an (...) improved account of quantificational binding, weak crossover, wh-questions, superiority, and polarity licensing. (shrink)

I propose the first strictly compositional semantic account of same. New data, including especially NP-internal uses such as two men with the same name, suggests that same in its basic use is a quantificational element taking scope over nominals. Given type-lifting as a generally available mechanism, I show that this follows naturally from the fact that same is an adjective. Independently-motivated assumptions extend the analysis to standard examples such as Anna and Bill read the same book via a mechanism I (...) call PARASITIC SCOPE, in which the scope of same depends on the scope of some other scopetaking element in the sentence. Although I will initially discuss the analysis in terms of a familiar Quantifier Raising framework, I go on to implement the analysis within an innovative continuation-based Type-Logical Grammar. The empirical payoff for dealing in continuations is that a simple generalization of the basic analysis gives the first ever formal account of cases in which same distributes over objects other than NP denotations, as in the relevant interpretation of John hit and killed the same man. (shrink)

This articles explores the mereological foundation of truthmaker semantics. Building upon Kit Fine’s abstract theory of part in [16], we engage in an exploration of the mereological assumptions that determine the construction of truthmaker semantics. Our approach yields semantics for a diverse range of logics, including substructural logics such as the associative Lambek calculus, as well as the logics of analytic containment. Furthermore, we elucidate the philosophical implications that arise from this pioneering approach.

This open access book is a superb collection of some fifteen chapters inspired by Schroeder-Heister's groundbreaking work, written by leading experts in the field, plus an extensive autobiography and comments on the various contributions by Schroeder-Heister himself. For several decades, Peter Schroeder-Heister has been a central figure in proof-theoretic semantics, a field of study situated at the interface of logic, theoretical computer science, natural-language semantics, and the philosophy of language. -/- The chapters of which this book is composed discuss the (...) subject from a rich variety of angles, including the history of logic, the proper interpretation of logical validity, natural deduction rules, the notions of harmony and of synonymy, the structure of proofs, the logical status of equality, intentional phenomena, and the proof theory of second-order arithmetic. All chapters relate directly to questions that have driven Schroeder-Heister's own research agenda and to which he has made seminal contributions. The extensive autobiographical chapter not only provides a fascinating overview of Schroeder-Heister's career and the evolution of his academic interests but also constitutes a contribution to the recent history of logic in its own right, painting an intriguing picture of the philosophical, logical, and mathematical institutional landscape in Germany and elsewhere since the early 1970s. The papers collected in this book are illuminatingly put into a unified perspective by Schroeder-Heister's comments at the end of the book. Both graduate students and established researchers in the field will find this book an excellent resource for future work in proof-theoretic semantics and related areas. (shrink)

We present a new frame semantics for positive relevant and substructural propositional logics. This frame semantics is both a generalisation of Routley–Meyer ternary frames and a simplification of them. The key innovation of this semantics is the use of a single accessibility relation to relate collections of points to points. Different logics are modeled by varying the kinds of collections used: they can be sets, multisets, lists or trees. We show that collection frames on trees are sound and complete for (...) the basic positive distributive substructural logic $\mathsf {B}^+$, that collection frames on multisets are sound and complete for $\mathsf {RW}^+$ (the relevant logic $\mathsf {R}^+$, without contraction, or equivalently, positive multiplicative and additive linear logic with distribution for the additive connectives), and that collection frames on sets are sound for the positive relevant logic $\mathsf {R}^+$. The completeness of set frames for $\mathsf {R}^+$ is, currently, an open question. (shrink)

What is the relation of logic to thinking? My dissertation offers a new argument for the claim that logic is constitutive of thinking in the following sense: representational activity counts as thinking only if it manifests sensitivity to logical rules. In short, thinking has to be minimally logical. An account of thinking has to allow for our freedom to question or revise our commitments – even seemingly obvious conceptual connections – without loss of understanding. This freedom, I argue, requires that (...) thinkers have general abilities to respond to support and tension among their thoughts. And these abilities are constituted by following logical rules. So thinkers have to follow logical rules. But there isn’t just one correct logic for thinking. I show that my view is consistent with logical pluralism: there are a range of correct logics, any one of which a thinker might follow. A logic for thinking does, however, have to contain certain minimal principles: Modus Ponens and Non-Contradiction, and perhaps others. We follow logical rules by exercising logical capacities, which display a distinctive first-person/third-person asymmetry: a subject can find the instances of a rule compelling without seeing them as instances of a rule. As a result, there are two limits on illogical thinking. First, thinkers have to tend to find instances of logical rules compelling. Second, thinkers can’t think in obviously illogical ways. So thinking has to be logical – but not perfectly so. When we try to think, but fail, we produce nonsense. But our failures to think are often subjectively indistinguishable from thinking. To explain how this occurs, I offer an account of nonsense. To be under the illusion that some nonsense makes sense is to enter a pretence that the nonsense is meaningful. Our use of nonsense within the pretence relies on the role of logical form in understanding. Finally, while the normativity of logic doesn’t fall directly out of logical constitutivism, it’s possible to build an attractive account of logical normativity which has logical constitutivism as an integral part. I argue that thinking is necessary for human flourishing, and that this is the source of logical normativity. (shrink)

Computational complexity is a discipline of computer science and mathematics which classifies computational problems depending on their inherent difficulty, i.e. categorizes algorithms according to their performance, and relates these classes to each other. P problems are a class of computational problems that can be solved in polynomial time using a deterministic Turing machine while solutions to NP problems can be verified in polynomial time, but we still do not know whether they can be solved in polynomial time as well. A (...) solution for the so-called NP-complete problems will also be a solution for any other such problems. Its artificial-intelligence analogue is the class of AI-complete problems, for which a complete mathematical formalization still does not exist. In this chapter we will focus on analysing computational classes to better understand possible formalizations of AI-complete problems, and to see whether a universal algorithm, such as a Turing test, could exist for all AI-complete problems. In order to better observe how modern computer science tries to deal with computational complexity issues, we present several different deep-learning strategies involving optimization methods to see that the inability to exactly solve a problem from a higher order computational class does not mean there is not a satisfactory solution using state-of-the-art machine-learning techniques. Such methods are compared to philosophical issues and psychological research regarding human abilities of solving analogous NP-complete problems, to fortify the claim that we do not need to have an exact and correct way of solving AI-complete problems to nevertheless possibly achieve the notion of strong AI. (shrink)

Restall set forth a "consecution" calculus in his "An Introduction to Substructural Logics." This is a natural deduction type sequent calculus where the structural rules play an important role. This paper looks at different ways of extending Restall's calculus. It is shown that Restall's weak soundness and completeness result with regards to a Hilbert calculus can be extended to a strong one so as to encompass what Restall calls proofs from assumptions. It is also shown how to extend the calculus (...) so as to validate the metainferential rule of reasoning by cases, as well as certain theory-dependent rules. (shrink)

The paper deals with the problem of logical adequacy of language knowledge with cognition of reality. A logical explication of the concept of language knowledge conceived of as a kind of codified knowledge is taken into account in the paper. Formal considerations regarding the notions of meta-knowledge (logical knowledge about language knowledge) and truth are developed in the spirit of some ideas presented in the author’s earlier papers (1991, 1998, 2001a,b, 2007a,b,c) treating about the notions of meaning, denotation and truthfulness (...) of well-formed expressions (wfes) of any given categorial language. Three aspects connected with knowledge codified in language are considered, including: 1) syntax and two kinds of semantics: intensional and extensional, 2) three kinds of non-standard language models and 3) three notions of truthfulness of wfes. Adequacy of language knowledge to cognitive objects is understood as an agreement of truthfulness of sentences in these three models. (shrink)

We argue that all comparative expressions in natural language obey a principle that we call Comparability: if x and y are at least as F as themselves, then either x is at least as F as y or y is at least as F as x. This principle has been widely rejected among philosophers, especially by ethicists, and its falsity has been claimed to have important normative implications. We argue that Comparability is needed to explain the goodness of several patterns (...) of inference that seem manifestly valid, that the purported failures of Comparability would have absurd consequences, and that the influential arguments against Comparability are less compelling than they may have initially seemed. (shrink)

The concept of linguistic infinity has had a central role to play in foundational debates within theoretical linguistics since its more formal inception in the mid-twentieth century. The conceptualist tradition, marshalled in by Chomsky and others, holds that infinity is a core explanandum and a link to the formal sciences. Realism/Platonism takes this further to argue that linguistics is in fact a formal science with an abstract ontology. In this paper, I argue that a central misconstrual of formal apparatus of (...) recursive operations such as the set-theoretic operation merge has led to a mathematisation of the object of inquiry, producing a strong analogy with discrete mathematics and especially arithmetic. The main product of this error has been the assumption that natural, like some formal, languages are discretely infinite. I will offer an alternative means of capturing the insights and observations related to this posit in terms of scientific modelling. My chief aim will be to draw from the larger philosophy of science literature in order to offer a position of grammars as models compatible with various foundational interpretations of linguistics while being informed by contemporary ideas on scientific modelling for the natural and social sciences. (shrink)

The main objective of the paper is to provide a conceptual apparatus of a general logical theory of language communication. The aim of the paper is to outline a formal-logical theory of language in which the concepts of the phenomenon of language communication and language communication in general are defined and some conditions for their adequacy are formulated. The theory explicates the key notions of contemporary syntax, semantics, and pragmatics. The theory is formalized on two levels: token-level and type-level. As (...) such, it takes into account the dual – token and type – ontological character of linguistic entities. The basic notions of the theory: language communication, meaning and interpretation are introduced on the second, type-level of formalization, and their required prior formalization of some of the notions introduced on the first, token-level; among others, the notion of an act of communication. Owing to the theory, it is possible to address the problems of adequacy of both empirical acts of communication and of language communication in general. All the conditions of adequacy of communication discussed in the presented paper, are valid for one-way communication (sender-recipient); nevertheless, they can also apply to the reverse direction of language communication (recipient-sender). Therefore, they concern the problem of two-way understanding in language communication. (shrink)

In the paper, original formal-logical conception of syntactic and semantic: intensional and extensional senses of expressions of any language L is outlined. Syntax and bi-level intensional and extensional semantics of language L are characterized categorically: in the spirit of some Husserl’s ideas of pure grammar, Leśniewski-Ajukiewicz’s theory syntactic/semantic categories and in accordance with Frege’s ontological canons, Bocheński’s famous motto—syntax mirrors ontology and some ideas of Suszko: language should be a linguistic scheme of ontological reality and simultaneously a tool of its (...) cognition. In the logical conception of language L, its expressions should satisfy some general conditions of language adequacy. The adequacy ensures their unambiguous syntactic and semantic senses and mutual, syntactic, and semantic compatibility, correspondence guaranteed by the acceptance of a postulate of categorial compatibility syntactic and semantic categories of expressions of L. From this postulate, three principles of compositionality follow: one syntactic and two semantic already known to Frege. They are treated as conditions of homomorphism partial algebra of L into algebraic models of L: syntactic, intensional, and extensional. In the paper, they are applied to some expressions with quantifiers. Language adequacy connected with the logical senses described in the logical conception of language L is, of course, an idealization, but only expressions with high degrees of precision of their senses, after due justification, may become theorems of science. (shrink)

Lecture notes from Husserl's logic lectures published during the last 20 years offer a much better insight into his doctrine of the forms of meaning than does the fourth Logical Investigation or any other work published during Husserl's lifetime. This paper provides a detailed reconstruction, based on all the sources now available, of Husserl's system of logical grammar. After having explained the notion of meaning that Husserl assumes in his later logic lectures as well as the notion of form of (...) meaning as it features in ‘doctrine of the forms of meaning’, I present a system of rules that describes all the various forms of meaning that Husserl singles out in his lectures. (shrink)

This work contributes to the theory of judgement aggregation by discussing a number of significant non-classical logics. After adapting the standard framework of judgement aggregation to cope with non-classical logics, we discuss in particular results for the case of Intuitionistic Logic, the Lambek calculus, Linear Logic and Relevant Logics. The motivation for studying judgement aggregation in non-classical logics is that they offer a number of modelling choices to represent agents’ reasoning in aggregation problems. By studying judgement aggregation in logics that (...) are weaker than classical logic, we investigate whether some well-known impossibility results, that were tailored for classical logic, still apply to those weak systems. (shrink)

Prioritized bases, i.e., weakly ordered sets of sentences, have been used for specifying an agent’s ‘basic’ or ‘explicit’ beliefs, or alternatively for compactly encoding an agent’s belief state without the claim that the elements of a base are in any sense basic. This paper focuses on the second interpretation and shows how a shifting of priorities in prioritized bases can be used for a simple, constructive and intuitive way of representing a large variety of methods for the change of belief (...) states—methods that have usually been characterized semantically by a system-of-spheres modeling. Among the methods represented are ‘radical’, ‘conservative’ and ‘moderate’ revision, ‘revision by comparison’ in its raising and lowering variants, as well as various constructions for belief expansion and contraction. Importantly, none of these methods makes any use of numbers. (shrink)

The paper enriches the conceptual apparatus of the theory of meaning and denotation that was presented in Part I (Section 3). This part concentrates on the notion of interpretation, which is defined as an equivalence class of the relation possessing the same manner of interpreting types. In this part, some relations between meaning and interpretation, as well as one between denotation an interpretational denotation are established. In the theory of meaning and interpretation, the notion of language communication has been formally (...) introduced and some conditions of correctness of communication have been formulated. (shrink)

Linear logic, introduced by Girard, is a refinement of classical logic with a natural, intrinsic accounting of resources. This accounting is made possible by removing the ‘structural’ rules of contraction and weakening, adding a modal operator and adding finer versions of the propositional connectives. Linear logic has fundamental logical interest and applications to computer science, particularly to Petri nets, concurrency, storage allocation, garbage collection and the control structure of logic programs. In addition, there is a direct correspondence between polynomial-time computation (...) and proof normalization in a bounded form of linear logic. In this paper we show that unlike most other propositional logics, full propositional linear logic is undecidable. Further, we prove that without the modal storage operator, which indicates unboundedness of resources, the decision problem becomes PSPACE-complete. We also establish membership in NP for the multiplicative fragment, NP-completeness for the multiplicative fragment extended with unrestricted weakening, and undecidability for fragments of noncommutative propositional linear logic. (shrink)

An axiomatics of the product-free syntactic calculus L ofLambek has been presented whose only rule is the cut rule. It was alsoproved that there is no finite axiomatics of that kind. The proofs weresubsequently simplified. Analogous results for the nonassociativevariant NL of L were obtained by Kandulski. InLambek's original version of the calculus, sequent antecedents arerequired to be nonempty. By removing this restriction, we obtain theextensions L 0 and NL 0 ofL and NL, respectively. Later, the finiteaxiomatization problem for L (...) 0 andNL 0 was partially solved, viz., for formulas withoutleft (or, equivalently, right) division and an (infinite) cut-ruleaxiomatics for the whole of L 0 has been given. Thepresent paper yields an analogous axiomatics forNL 0. Like in the author's previous work, the notionof rank of an axiom is introduced which, although inessentialfor the results given below, may be useful for the expectednonfinite-axiomatizability proof. (shrink)

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)

We present a labelled version of Lambek Calculus without unit, and we use it to prove a completeness theorem for Lambek Calculus with respect to some relational semantics.

K-axiom-based epistemic closure for explicit knowledge is rejected for even the most trivial cases of deductive inferential reasoning on account of the fact that the closure axiom does not extend beyond a raw consequence relation. The recognition that deductive inference concerns interaction as much as it concerns consequence allows for perspectives from logics of multi-agent information flow to be refocused onto mono-agent deductive reasoning. Instead of modeling the information flow between different agents in a communicative or announcement setting, we model (...) the information flow between different states of a single agent as that agent reasons deductively. The resource management of the database of agent states for the deductive reasoning fragment in question is covered by the residuated structure that encodes the nonassociative Lambek Calculus with permutation, bottom, and identity: NLP01. (shrink)

ABSTRACTMonoidal logics were introduced as a foundational framework to analyze the proof theory of logical systems. Inspired by Lambek's seminal work in categorical logic, the objective is to defin...

Discontinuity refers to the character of many natural language constructions wherein signs differ markedly in their prosodic and semantic forms. As such it presents interesting demands on monostratal computational formalisms which aspire to descriptive adequacy. Pied piping, in particular, is argued by Pollard (1988) to motivate phrase structure-style feature percolation. In the context of categorial grammar, Bach (1981, 1984), Moortgat (1988, 1990, 1991) and others have sought to provide categorial operators suited to discontinuity. These attempts encounter certain difficulties with respect (...) to model theory and/or proof theory, difficulties which the current proposals are intended to resolve.Lambek calculus is complete for interpretation byresiduation with respect to the adjunction operation of groupoid algebras (Buszkowski 1986). In Moortgat and Morrill (1991) it is shown how to give calculi for families of categorial operators, each defined by residuation with respect to an operation of prosodic adjunction (associative, non-associative, or with interactive axioms). The present paper treats discontinuity in this way, by residuation with respect to three adjunctions: + (associative), (.,.) (split-point marking), andW (wrapping) related by the equations 1+s 2+s 3=(s 1,s 3)Ws 2. We show how the resulting methods apply to discontinuous functors, quantifier scope and quantifier scope ambiguity, pied piping, and subject and object antecedent reflexivisation. (shrink)

We give a proof-theoretic and algorithmic complexity analysis for systems introduced by Morrill to serve as the core of the CatLog categorial grammar parser. We consider two recent versions of Morrill’s calculi, and focus on their fragments including multiplicative (Lambek) connectives, additive conjunction and disjunction, brackets and bracket modalities, and the! subexponential modality. For both systems, we resolve issues connected with the cut rule and provide necessary modifications, after which we prove admissibility of cut (cut elimination theorem). We also prove (...) algorithmic undecidability for both calculi, and show that categorial grammars based on them can generate arbitrary recursively enumerable languages. (shrink)

Monoidal logics were introduced as a foundational framework to analyse the proof theory of deontic logic. Building on Lambek’s work in categorical logic, logical systems are defined as deductive systems, that is, as collections of equivalence classes of proofs satisfying specific rules and axiom schemata. This approach enables the classification of deductive systems with respect to their categorical structure. When looking at their proof theory, however, one can see that there are similarities between monoidal and substructural logics. The purpose of (...) the present paper is to address this issue and highlight the differences between these two approaches. We argue that monoidal logics provide a more flexible foundational framework that enables a finer analysis of the relationship between negation and other logical connectives. We show that the elimination of double negation is independent from the de Morgan dualities, that monoidal deductive systems are not necessarily weakly distributive and that deduc... (shrink)