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)

Against the backdrop of the frequent comparison of theories of truth in the literature on semantic paradoxes with regard to which inferences and metainferences are deemed valid, this paper develops a novel approach to defining a binary predicate for representing the valid inferences and metainferences of a theory within the theory itself under the assumption that the theory is defined with a classical meta-theory. The aim with the approach is to obtain a tool which facilitates the comparison between a theory (...) and its competitors within the theory itself, thereby expressing the disagreement between the theories within the theories. After discussing what we can and should require of an object-linguistic representation of a theory for that purpose, this paper proposes to restrict the representation of valid metainferences to locally valid metainferences, a requirement which turns out to be \-consistent and conservative over classical first-order arithmetic. This approach is then applied to four theories definable on strong Kleene models using a labelled nested sequent calculus. (shrink)

We study the computational complexity of the universal and quasi-equational theories of classes of bounded distributive lattices with a negation operation, i.e., a unary operation satisfying a subset of the properties of the Boolean negation. The upper bounds are obtained through the use of partial algebras. The lower bounds are either inherited from the equational theory of bounded distributive lattices or obtained through a reduction of a global satisfiability problem for a suitable system of propositional modal logic.

This paper contains a proof-theoretic account of unification in transitive reflexive modal logics, which means that the reasoning is syntactic and uses as little semantics as possible. New proofs of theorems on unification types are presented and these results are extended to negationless fragments. In particular, a syntactic proof of Ghilardi’s result that $\mathsf {S4}$ has finitary unification is provided. In this approach the relation between classical valuations, projective unifiers, and admissible rules is clarified.

We study the computational complexity of the universal theory of residuated ordered groupoids, which are algebraic structures corresponding to Nonassociative Lambek Calculus. We prove that the universal theory is co $$\textsf {NP}$$ -complete which, as we observe, is the lowest possible complexity for a universal theory of a non-trivial class of structures. The universal theories of the classes of unital and integral residuated ordered groupoids are also shown to be co $$\textsf {NP}$$ -complete. We also prove the co $$\textsf {NP}$$ (...) -completeness of the universal theory of classes of residuated algebras, algebraic structures corresponding to Generalized Lambek Calculus. (shrink)