We apply the theory of partial algebras, following the approach developed by Van Alten, to the study of the computational complexity of universal theories of monotonic and normal modal algebras. We show how the theory of partial algebras can be deployed to obtain co-NP and EXPTIME upper bounds for the universal theories of, respectively, monotonic and normal modal algebras. We also obtain the corresponding lower bounds, which means that the universal theory of monotonic modal algebras is co-NP-complete and the universal (...) theory of normal modal algebras is EXPTIME-complete. It also follows that the quasi-equational theory of monotonic modal algebras is co-NP-complete. While the EXPTIME upper bound for the universal theory of normal modal algebras can be obtained in a more straightforward way, as discussed in the paper, due to its close connection to the equational theory of normal modal algebras with the universal modality operator, the technique based on the theory of partial algebras is applicable to the study of universal theories of algebras corresponding to a wide range of logics with intensional operators, where no such connection is available. (shrink)

In this paper, the predicate counterparts, defined both axiomatically and semantically by means of Kripke frames, of the modal propositional logics $\textbf {GL}$, $\textbf {Grz}$, $\textbf {wGrz}$ and their extensions are considered. It is proved that the set of semantical consequences on Kripke frames of every logic between $\textbf {QwGrz}$ and $\textbf {QGL.3}$ or between $\textbf {QwGrz}$ and $\textbf {QGrz.3}$ is $\Pi ^1_1$-hard even in languages with three (sometimes, two) individual variables, two (sometimes, one) unary predicate letters, and a single (...) proposition letter. As a corollary, it is proved that infinite families of modal predicate axiomatic systems, based on the classical first-order logic and the modal propositional logics $\textbf {GL}$, $\textbf {Grz}$, $\textbf {wGrz}$ are not Kripke complete. Both $\Pi ^1_1$-hardness and Kripke incompleteness results of the paper do not depend on whether the logics contain the Barcan formula. (shrink)

The SRL of King is a sound, complete and decidable logic designed specifically to support formalisms for the HPSG of Pollard and Sag. The SRL notion of modellability in a signature is particularly important for HPSG, and the present paper modifies an elegant method due to Blackburn and Spaan in order to prove that – modellability in each computable signature is 1 0 – modellability in some finite signature is 1 0 -hard, and – modellability in some finite signature is (...) decidable. (shrink)

We investigate the effect on the complexity of adding the universal modality and the reflexive transitive closure modality to modal logics. From the examples in the literature, one might conjecture that adding the reflexive transitive closure modality is at least as hard as adding the universal modality, and that adding either of these modalities to a multi-modal logic where the modalities do not interact can only increase the complexity to EXPTIME-complete. We show that the first conjecture holds under reasonable assumptions (...) and that, except for a number of special cases which we fully characterize, the hardness part of the second conjecture is true. However, the upper bound part of the second conjecture fails miserably: we show that there exists a uni-modal, decidable, finitely axiomatizable, and canonical logic for which adding the universal modality causes undecidability and for which adding the reflexive transitive closure modality causes high undecidability. (shrink)

This paper gives a simple method for providing categorial brands of feature-based unification grammars with a model-theoretic semantics. The key idea is to apply the paradigm of fibred semantics (or layered logics, see Gabbay (1990)) in order to combine the two components of a feature-based grammar logic. We demonstrate the method for the augmentation of Lambek categorial grammar with Kasper/Rounds-style feature logic. These are combined by replacing (or annotating) atomic formulas of the first logic, i.e. the basic syntactic types, by (...) formulas of the second. Modelling such a combined logic is less trivial than one might expect. The direct application of the fibred semantics method where a combined atomic formula like np (num: sg & pers: 3rd) denotes those strings which have the indicated property and the categorial operators denote the usual left- and right-residuals of these string sets, does not match the intuitive, unification-based proof theory. Unification implements a global bookkeeping with respect to a proof whereas the direct fibring method restricts its view to the atoms of the grammar logic. The solution is to interpret the (embedded) feature terms as global feature constraints while maintaining the same kind of fibred structures. For this adjusted semantics, the anticipated proof system is sound and complete. (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)