Amalgamation and interpolation in ordered algebras

The first part of this paper provides a comprehensive and self-contained account of the interrelationships between algebraic properties of varieties and properties of their free algebras and equational consequence relations. In particular, proofs are given of known equivalences between the amalgamation property and the Robinson property, the congruence extension property and the extension property, and the flat amalgamation property and the deductive interpolation property, as well as various dependencies between these properties. These relationships are then exploited in the second part of the paper in order to provide new proofs of amalgamation and deductive interpolation for the varieties of lattice-ordered abelian groups and MV-algebras, and to determine important subvarieties of residuated lattices where these properties hold or fail. In particular, a full description is given of all subvarieties of commutative GMV-algebras possessing the amalgamation property.

Sheaf representations of MV-algebras and lattice-ordered abelian groups via duality

We study representations of MV-algebras -- equivalently, unital lattice-ordered abelian groups -- through the lens of Stone-Priestley duality, using canonical extensions as an essential tool. Specifically, the theory of canonical extensions implies that the (Stone-Priestley) dual spaces of MV-algebras carry the structure of topological partial commutative ordered semigroups. We use this structure to obtain two different decompositions of such spaces, one indexed over the prime MV-spectrum, the other over the maximal MV-spectrum. These decompositions yield sheaf representations of MV-algebras, using a new and purely duality-theoretic result that relates certain sheaf representations of distributive lattices to decompositions of their dual spaces. Importantly, the proofs of the MV-algebraic representation theorems that we obtain in this way are distinguished from the existing work on this topic by the following features: (1) we use only basic algebraic facts about MV-algebras; (2) we show that the two aforementioned sheaf representations are special cases of a common result, with potential for generalizations; and (3) we show that these results are strongly related to the structure of the Stone-Priestley duals of MV-algebras. In addition, using our analysis of these decompositions, we prove that MV-algebras with isomorphic underlying lattices have homeomorphic maximal MV-spectra. This result is an MV-algebraic generalization of a classical theorem by Kaplansky stating that two compact Hausdorff spaces are homeomorphic if, and only if, the lattices of continuous [0, 1]-valued functions on the spaces are isomorphic.

Admissibility in Finitely Generated Quasivarieties

Checking the admissibility of quasiequations in a finitely generated (i.e., generated by a finite set of finite algebras) quasivariety Q amounts to checking validity in a suitable finite free algebra of the quasivariety, and is therefore decidable. However, since free algebras may be large even for small sets of small algebras and very few generators, this naive method for checking admissibility in Q is not computationally feasible. In this paper, algorithms are introduced that generate a minimal (with respect to a multiset well-ordering on their cardinalities) finite set of algebras such that the validity of a quasiequation in this set corresponds to admissibility of the quasiequation in Q. In particular, structural completeness (validity and admissibility coincide) and almost structural completeness (validity and admissibility coincide for quasiequations with unifiable premises) can be checked. The algorithms are illustrated with a selection of well-known finitely generated quasivarieties, and adapted to handle also admissibility of rules in finite-valued logics.

A Logical Descriptor for Regular Languages via Stone Duality

In this paper we introduce a class of descriptors for regular languages arising from an application of the Stone duality between finite Boolean algebras and finite sets. These descriptors, called classical fortresses, are object specified in classical propositional logic and capable to accept exactly regular languages. To prove this, we show that the languages accepted by classical fortresses and deterministic finite automata coincide. Classical fortresses, besides being propositional descriptors for regular languages, also turn out to be an efficient tool for providing alternative and intuitive proofs for the closure properties of regular languages.

Admissibility via natural dualities

It is shown that admissible clauses and quasi-identities of quasivarieties generated by a single finite algebra, or equivalently, the quasiequational and universal theories of their free algebras on countably infinitely many generators, may be characterized using natural dualities. In particular, axiomatizations are obtained for the admissible clauses and quasi-identities of bounded distributive lattices, Stone algebras, Kleene algebras and lattices, and De Morgan algebras and lattices.

Applicative theories for logarithmic complexity classes

We present applicative theories of words corresponding to weak, and especially logarithmic, complexity classes. The theories for the logarithmic hierarchy and alternating logarithmic time formalise function algebras with concatenation recursion as main principle. We present two theories for logarithmic space where the first formalises a new two-sorted algebra which is very similar to Cook and Bellantoni's famous two-sorted algebra B for polynomial time [4]. The second theory describes logarithmic space by formalising concatenation- and sharply bounded recursion. All theories contain the predicates WW representing words, and VV representing temporary inaccessible words. They are inspired by Cantini's theories [6] formalising B.