In the proof-theoretic semantics approach to meaning, harmony , requiring a balance between introduction-rules (I-rules) and elimination rules (E-rules) within a meaning conferring natural-deduction proof-system, is a central notion. In this paper, we consider two notions of harmony that were proposed in the literature: 1. GE-harmony , requiring a certain form of the E-rules, given the form of the I-rules. 2. Local intrinsic harmony : imposes the existence of certain transformations of derivations, known as reduction and expansion . We propose (...) a construction of the E-rules (in GE-form) from given I-rules, and prove that the constructed rules satisfy also local intrinsic harmony. The construction is based on a classification of I-rules, and constitute an implementation to Gentzen’s (and Pawitz’) remark, that E-rules can be “read off” I-rules. (shrink)
The paper briefly surveys the sentential proof-theoretic semantics for fragment of English. Then, appealing to a version of Frege’s context-principle (specified to fit type-logical grammar), a method is presented for deriving proof-theoretic meanings for sub-sentential phrases, down to lexical units (words). The sentential meaning is decomposed according to the function-argument structure as determined by the type-logical grammar. In doing so, the paper presents a novel proof-theoretic interpretation of simple type, replacing Montague’s model-theoretic type interpretation (in arbitrary Henkin models). The domains (...) of derivations are collections of derivations in the associated “dedicated” natural-deduction proof-system, and functions therein (with no appeal to models, truth-values and elements of a domain). The compositionality of the semantics is analyzed. (shrink)
The paper exposes the relevance of permuting conversions (in natural-deduction systems) to the role of such systems in the theory of meaning known as proof-theoretic semantics, by relating permuting conversion to harmony, hitherto related to normalisation only. This is achieved by showing the connection of permuting conversion to the general notion of canonicity, once applied to arbitrary derivations from open assumption. In the course of exposing the relationship of permuting conversions to harmony, a general definition of the former is proposed, (...) generalising the specific cases of disjunction and existential quantifiers considered in the literature. (shrink)
The paper presents a proof-theoretic semantics (PTS) for a fragment of natural language, providing an alternative to the traditional model-theoretic (Montagovian) semantics (MTS), whereby meanings are truth-condition (in arbitrary models). Instead, meanings are taken as derivability-conditions in a dedicated natural-deduction (ND) proof-system. This semantics is effective (algorithmically decidable), adhering to the meaning as use paradigm, not suffering from several of the criticisms formulated by philosophers of language against MTS as a theory of meaning. In particular, Dummett’s manifestation argument does not (...) obtain, and assertions are always warranted, having grounds of assertion. The proof system is shown to satisfy Dummett’s harmony property, justifying the ND rules as meaning conferring. The semantics is suitable for incorporation into computational linguistics grammars, formulated in type-logical grammar. (shrink)
The paper proposes a semantic value for the logical constants (connectives and quantifiers) within the framework of proof-theoretic semantics, basic meaning on the introduction rules of a meaning conferring natural deduction proof system. The semantic value is defined based on Fregecontributions” to sentential meanings as determined by the function-argument structure as induced by a type-logical grammar. In doing so, the paper proposes a novel proof-theoretic interpretation of the semantic types, traditionally interpreted in Henkin models. The compositionality of the resulting attribution (...) of semantic values is discussed. Elsewhere, the same method was used for defining proof-theoretic meaning of subsentential phrases in a fragment of natural language. Doing the same for (the simpler and clearer case of) logic sheds more light on the proposal. (shrink)
The paper studies the extension of harmony and stability, major themes in proof-theoretic semantics, from single-conclusion natural-deduction systems to multiple -conclusions natural-deduction, independently of classical logic. An extension of the method of obtaining harmoniously-induced general elimination rules from given introduction rules is suggested, taking into account sub-structurality. Finally, the reductions and expansions of the multiple -conclusions natural-deduction representation of classical logic are formulated.
The paper suggests a revision of the notion of harmony, a major necessary condition in proof-theoretic semantics for a natural-deduction proof-system to qualify as meaning conferring, when moving to a bilateral proof-system. The latter considers both forces of assertion and denial as primitive, and is applied here to positive logics, lacking negation altogether. It is suggested that in addition to the balance between (positive) introduction and elimination rules traditionally imposed by harmony, a balance should be imposed also on: (i) negative (...) introduction and elimination rules, and (ii) positive and negative introduction rules. The paper suggests a proof-theoretical definition of duality (not referring to truthtables), using which double harmony is defined. The paper proves that in a doubly-harmonious system, the coordination rule, typical to bilateral systems, is admissible. (shrink)
In this paper, we show how the problem of accounting for the semanticsof temporal preposition phrases (tPPs) leads us to some surprisinginsights into the semantics of temporal expressions ingeneral. Specifically, we argue that a systematic treatment of EnglishtPPs is greatly facilitated if we endow our meaning assignments with context variables, a device which allows a tPP to restrict domainsof quantification arising elsewhere in a sentence. We observe that theuse of context variables implies that tPPs can modify expressions intwo ways, and (...) we use this observation to predict the behaviour of tPPswhose complements are themselves modified by other tPPs. (shrink)
The paper presents a generalization of pregroup, by which a freely-generated pregroup is augmented with a finite set of commuting inequations, allowing limited commutativity and cancelability. It is shown that grammars based on the commutation-augmented pregroups generate mildly context-sensitive languages. A version of Lambek’s switching lemma is established for these pregroups. Polynomial parsability and semilinearity are shown for languages generated by these grammars.
The paper proposes a semantics for contextual (i.e., Temporal and Locative) Prepositional Phrases (CPPs) like during every meeting, in the garden, when Harry met Sally and where I’m calling from. The semantics is embodied in a multi-modal extension of Combinatory Categoral Grammar (CCG). The grammar allows the strictly monotonic compositional derivation of multiple correct interpretations for “stacked” or multiple CPPs, including interpretations whose scope relations are not what would be expected on standard assumptions about surfacesyntactic command and monotonic derivation. A (...) type-hierarchy of functional modalities plays a crucial role in the specification of the fragment. (shrink)
We show that the relational semantics of the Lambek calculus, both nonassociative and associative, is also sound and complete for its extension with classical propositional logic. Then, using filtrations, we obtain the finite model property for the nonassociative Lambek calculus extended with classical propositional logic.
I argue in favour of object languages of logics to be diversely-generated, that is, not having identical immediate sub-formulas. In addition to diversely-generated object languages constituting a more appropriate abstraction of the use of sentential connectives in natural language, I show that such language lead to a simplifications w.r.t. some specific issues: the identity of proofs, the factual equivalence and the Mingle axiom in Relevance logics. I also point out that some of the properties of classical logic based on freely-generated (...) object languagest. (shrink)
Unification grammars are known to be Turing-equivalent; given a grammar G and a word w, it is undecidable whether w L(G). In order to ensure decidability, several constraints on grammars, commonly known as off-line parsability (OLP), were suggested, such that the recognition problem is decidable for grammars which satisfy OLP. An open question is whether it is decidable if a given grammar satisfies OLP. In this paper we investigate various definitions of OLP and discuss their interrelations, proving that some of (...) the OLP variants are indeed undecidable. We then present a novel, decidable OLP constraint which is more liberal than the existing decidable ones. (shrink)
In this paper, we propose a game semantics for the (associative) Lambek calculus . Compared to the implicational fragment of intuitionistic propositional calculus, the semantics deals with two features of the logic: absence of structural rules, as well as directionality of implication. We investigate the impact of these variations of the logic on its game semantics.
This paper develops a version of Natural Logic – an inference system that works directly on natural language syntactic representations, with no intermediate translation to logical formulae. Following work by Sánchez, we develop a small fragment that computes semantic order relations between derivation trees in Categorial Grammar. The proposed system has the following new characteristics: It uses orderings between derivation trees as purely syntactic units, derivable by a formal calculus. The system is extended for conjunctive phenomena like coordination and relative (...) clauses. This allows a simple account of non-monotonic expressions that are reducible to conjunctions of monotonic ones. A decision procedure for provability is developed for a fragment of Natural Logic. (shrink)
In this paper, we propose an extension of free pregroups with lower bounds on sets of pregroup elements. Pregroup grammars based on such pregroups provide a kind of an algebraic counterpart to universal quantification over type-variables. In particular, we show how our pregroup extensions can be used for pregroup grammars expressing natural-language coordination and extraction.
This paper develops an inference system for natural language within the ‘Natural Logic’ paradigm as advocated by van Benthem, Sánchez and others. The system that we propose is based on the Lambek calculus and works directly on the Curry-Howard counterparts for syntactic representations of natural language, with no intermediate translation to logical formulae. The Lambek -based system we propose extends the system by Fyodorov et~al., which is based on the Ajdukiewicz/Bar-Hillel calculus Bar Hillel,. This enables the system to deal with (...) new kinds of inferences, involving relative clauses, non-constituent coordination, and meaning postulates that involve complex expressions. Basing the system on the Lambek calculus leads to problems with non-normalized proof terms, which are treated by using normalization axioms. (shrink)
A semantics with plural entitles and plural times accounts for cumulative relations between plural arguments and temporal expressions. The semantics equips nominal, verbal and sentential meanings with temporal context variables and treats temporal modifiers as temporal generalized quantifiers; cumulative conjunction, however, takes place at types lower than generalized quantifiers. The mediation of temporal context variables allows cumulative relations to percolate between an argument in a main clause and one in a temporal clause, in apparent violation of locality restrictions. Plural times (...) form a semilattice structure imposed on the set of intervals; no interaction is observed between this and the internal temporal structure of intervals. (shrink)
The paper provides a proof-theory for a negative presentation of classical logic based on a single primitive of exclusion, generalizing the known presentation via the binary ‘nand. The completeness is established via deductive equivalence to Gentzens NK/LK systems.
Typed feature structures are used extensively for the specification of linguistic information in many formalisms. The subsumption relation orders TFSs by their information content. We prove that subsumption of acyclic TFSs is well founded, whereas in the presence of cycles general TFS subsumption is not well founded. We show an application of this result for parsing, where the well-foundedness of subsumption is used to guarantee termination for grammars that are off-line parsable. We define a new version of off-line parsability that (...) is less strict than the existing one; thus termination is guaranteed for parsing with a larger set of grammars. (shrink)
Inspired by the grammar of natural language, the paper presents a variant of first-order logic, in which quantifiers are not sentential operators, but are used as subnectors . A quantified term formed by a subnector is an argument of a predicate. The logic is defined by means of a meaning-conferring natural-deduction proof-system, according to the proof-theoretic semantics program. The harmony of the I/E-rules is shown. The paper then presents a translation, called the Frege translation, from the defined logic to standard (...) first-order logic, and shows that the proof-theoretic meanings of both logics coincide. The paper criticizes Frege’s original regimentation of quantified sentences of natural language, and argues for advantages of the proposed variant. (shrink)
The paper introduces a proof-theoretic semantics for adjectival modification as an alternative to the traditional model-theoretic semantics basing meaning on truth-conditions. The paper considers the proof-theoretic meaning of modification by means of the three traditional adjective classes: intersective, subsective and privative. It does so by introducing a meaning-conferring natural-deduction proof system for such modification. The PTS theory of meaning is not polluted by ontological commitments, for example, a scale for beauty and a yardstick for being beautiful. It only uses syntactic (...) artefacts of the proof language. The paper also defines, by suitable rules, iterated modification, shedding light on the relationship between iteration and adjectival classes. Modification via coordinated adjectives is covered too. An appendix delineates briefly the main ingredients of PTS. (shrink)
I show that in the context of proof-theoretic semantics, Dummett’s distinction between the assertoric meaning of a sentence and its ingredient sense can be seen as a distinction between two proof-theoretic meanings of a sentence: 1.Meaning as a conclusion of an introduction rule in a meaning-conferring natural-deduction proof system. 2.Meaning as a premise of an introduction rule in a meaning-conferring natural-deduction proof system. The effect of this distinction on compositionality of proof-theoretic meaning is discussed.
In this paper I introduce the notion of bilogics, namely logics interpreted over a pair of structures, in contrast to classical logic and many of its variations, the formulae of which are interpreted over one structure. In particular, I introduce and study Contrastive Logic, suitable for expressing contrast and conformity between the two structures involved.A major reason for this study is striving towards an extension of truth-conditional semantics to cover several natural-language particles, which have been hitherto considered not to be (...) amenable to such an extensional treatment, and were delegated to the level of non-extensional pragmatics. Examples of such particles are but and already. (shrink)
We define an automata-theoretic counterpart of grammars based on the Lambek-calculus L, a prominent formalism in computational linguistics. While the usual push-down automaton has the same weak generative power as the L-based grammars , there is no direct relationship between the computations of a PDA for some language L and the derivations of an L-based grammar for L. In the Lambek-automaton, on the other hand, there is a tight relation between automaton computations and grammar derivations. The automaton exhibits a novel (...) mode of operation, using hypothetical steps, directly inspired by the hypothetical reasoning embodied by L. (shrink)