Search

Join-preserving maps on the discrete time scale $\omega^+$, referred to as time warps, have been proposed as graded modalities that can be used to quantify the growth of information in the course of program execution. The set of time warps forms a simple distributive involutive residuated lattice -- called the time warp algebra -- that is equipped with residual operations relevant to potential applications. In this paper, we show that although the time warp algebra generates a variety that lacks the finite model property, it nevertheless has a decidable equational theory. We also describe an implementation of a procedure for deciding equations in this algebra, written in the OCaml programming language, that makes use of the Z3 theorem prover.

We show that under certain conditions, well-studied algebraic properties transfer from the class $\mathcal{Q}_{_\text{RFSI}}$ of the relatively finitely subdirectly irreducible members of a quasivariety $\mathcal{Q}$ to the whole quasivariety, and, in certain cases, back again. First, we prove that if $\mathcal{Q}$ is relatively congruence-distributive, then it has the $\mathcal{Q}$-congruence extension property if and only if $\mathcal{Q}_{_\text{RFSI}}$ has this property. We then prove that if $\mathcal{Q}$ has the $\mathcal{Q}$-congruence extension property and $\mathcal{Q}_{_\text{RFSI}}$ is closed under subalgebras, then $\mathcal{Q}$ has a one-sided amalgamation property (equivalently, for $\mathcal{Q}$, the amalgamation property) if and only if $\mathcal{Q}_{_\text{RFSI}}$ has this property. We also establish similar results for the transferable injections property and strong amalgamation property. For each property considered, we specialize our results to the case where $\mathcal{Q}$ is a variety -- so that $\mathcal{Q}_{_\text{RFSI}}$ is the class of finitely subdirectly irreducible members of $\mathcal{Q}$ and the $\mathcal{Q}$-congruence extension property is the usual congruence extension property -- and prove that when $\mathcal{Q}$ is finitely generated and congruence-distributive, and $\mathcal{Q}_{_\text{RFSI}}$ is closed under subalgebras, possession of the property is decidable. Finally, as a case study, we provide a complete description of the subvarieties of a notable variety of BL-algebras that have the amalgamation property., Comment: Expanded version that generalizes the main results to quasivarieties

The one-variable fragment of any first-order logic may be considered as a modal logic, where the universal and existential quantifiers are replaced by a box and diamond modality, respectively. In several cases, axiomatizations of algebraic semantics for these logics have been obtained: most notably, for the modal counterparts S5 and MIPC of the one-variable fragments of first-order classical logic and intuitionistic logic, respectively. Outside the setting of first-order intermediate logics, however, a general approach is lacking. This paper provides the basis for such an approach in the setting of first-order lattice-valued logics, where formulas are interpreted in algebraic structures with a lattice reduct. In particular, axiomatizations are obtained for modal counterparts of one-variable fragments of a broad family of these logics by generalizing a functional representation theorem of Bezhanishvili and Harding for monadic Heyting algebras. An alternative proof-theoretic proof is also provided for one-variable fragments of first-order substructural logics that have a cut-free sequent calculus and admit a certain bounded interpolation property.

The one-variable fragment of any first-order logic may be considered as a modal logic, where the universal and existential quantifiers are replaced by a box and diamond modality, respectively. In several cases, axiomatizations of algebraic semantics for these logics have been obtained: most notably, for the modal counterparts S5 and MIPC of the one-variable fragments of first-order classical logic and intuitionistic logic, respectively. Outside the setting of first-order intermediate logics, however, a general approach is lacking. This paper provides the basis for such an approach in the setting of first-order lattice-valued logics, where formulas are interpreted in algebraic structures with a lattice reduct. In particular, axiomatizations are obtained for modal counterparts of one-variable fragments of a broad family of these logics by generalizing a functional representation theorem of Bezhanishvili and Harding for monadic Heyting algebras. An alternative proof-theoretic proof is also provided for one-variable fragments of first-order substructural logics that have a cut-free sequent calculus and admit a certain bounded interpolation property.

We prove that an inverse-free equation is valid in the variety LG of lattice-ordered groups (L-groups) if and only if it is valid in the variety DLM of distributive latticeordered monoids (distributive L-monoids). This contrasts with the fact that, as proved by Repnitskii, there exist inverse-free equations that are valid in all Abelian L-groups but not in all commutative distributive L-monoids, and, as we prove here, there exist inverse-free equations that are valid in all totally ordered groups but not in all totally ordered monoids. We also prove that DLM has the finite model property and a decidable equational theory, establish a correspondence between the validity of equations in DLM and the existence of certain right orders on free monoids, and provide an effective method for reducing the validity of equations in LG to the validity of equations in DLM.

Graded modalities have been proposed in recent work on programming languages as a general framework for refining type systems with intensional properties. In particular, continuous endomaps of the discrete time scale, or time warps, can be used to quantify the growth of information in the course of program execution. Time warps form a complete residuated lattice, with the residuals playing an important role in potential programming applications. In this paper, we study the algebraic structure of time warps, and prove that their equational theory is decidable, a necessary condition for their use in real-world compilers. We also describe how our universal-algebraic proof technique lends itself to a constraint-based implementation, establishing a new link between universal algebra and verification technology., Comment: 22 pages, version accepted at RAMICS 2021 plus appendices

We introduce a universal algebraic generalization of de Jongh's notion of dependence for formulas of intuitionistic propositional logic, relating it to a notion of dependence defined by Marczewski for elements of an algebraic structure. Following ideas of de Jongh and Chagrova, we show how constructive proofs of (weak forms of) uniform interpolation can be used to decide dependence for varieties of abelian l-groups, MV-algebras, semigroups, and modal algebras. We also consider minimal provability results for dependence, obtaining in particular a complete description and decidability of dependence for the variety of lattices.

A many-valued modal logic is introduced that combines the usual Kripke frame semantics of the modal logic K with connectives interpreted locally at worlds by lattice and group operations over the real numbers. A labelled tableau system is provided and a coNEXPTIME upper bound obtained for checking validity in the logic. Focussing on the modal-multiplicative fragment, the labelled tableau system is then used to establish completeness for a sequent calculus that admits cut-elimination and an axiom system that extends the multiplicative fragment of Abelian logic., Logical Methods in Computer Science ; Volume 14, Issue 1 ; 1860-5974

The admissible rules of a logic (understood as a structural consequence relation) may be described as rules that can be added to the logic without producing any new theorems or equivalently as rules such that any substitution making the premises into theorems also makes the conclusion into a theorem. However this equivalence collapses once multiple conclusion or other more exotic admissible rules are considered. The first aim of this paper is to explain how such distinctions can be explained and characterized. The second aim is to explore how these rules can be useful in determining properties of classes of algebras.

Analytic proof calculi are introduced for box and diamond fragments of basic modal fuzzy logics that combine the Kripke semantics of modal logic K with the many-valued semantics of G��del logic. The calculi are used to establish completeness and complexity results for these fragments.