Abstract Using a variation of the rainbow construction and various pebble and colouring games, we prove that RRA, the class of all representable relation algebras, cannot be axiomatised by any first-order relation algebra theory of bounded quantifier depth. We also prove that the class At(RRA) of atom structures of representable, atomic relation algebras cannot be defined by any set of sentences in the language of RA atom structures that uses only a finite number of variables.

Relation algebra and its reducts provide us with a strong tool for reasoning about nondeterministic programs and their partial correctness. Demonic calculus, introduced to model the behaviour of a machine where the demon is in control of nondeterminism, has also provided us with an extension of that reasoning to total correctness. We formalise the framework for relational reasoning about total correctness in nondeterministic programs using semigroups with ordinary composition and demonic lattice operations. We show that the class of representable demonic join semigroups is not finitely axiomatisable and that the representation class of demonic meet semigroups does not have the finite representation property for its finite members. For lattice semigroups (with composition, demonic join and demonic meet) we show that the representation problem for finite algebras is undecidable, moreover the finite representation problem is also undecidable. It follows that the representation class is not finitely axiomatisable, furthermore the finite representation property fails.

Abstract We consider Minkowski spacetime, the set of all point-events of spacetime under the relation of causal accessibility. That is, x can access y if an electromagnetic or (slower than light) mechanical signal could be sent from x to y. We use Prior’s tense language of F and P representing causal accessibility and its converse relation. We consider two versions, one where the accessibility relation is reflexive and one where it is irreflexive. In either case it has been an open problem, for decades, whether the logic is decidable or axiomatisable. We make a small step forward by proving, in each case, that the set of valid formulas over two-dimensional Minkowski spacetime is decidable and that the complexity of each problem is PSPACE-complete. A consequence is that the temporal logic of intervals with real endpoints under either the containment relation or the strict containment relation is PSPACE-complete, the same is true if the interval accessibility relation is “each endpoint is not earlier”, or its irreflexive restriction. We provide a temporal formula that distinguishes between three-dimensional and two-dimensional Minkowski spacetime and another temporal formula that distinguishes the two-dimensional case where the underlying field is the real numbers from the case where instead we use the rational numbers.

Disjoint union is a partial binary operation returning the union of two sets if they are disjoint and undefined otherwise. A disjoint-union partial algebra of sets is a collection of sets closed under disjoint unions, whenever they are defined. We provide a recursive first-order axiomatisation of the class of partial algebras isomorphic to a disjoint-union partial algebra of sets but prove that no finite axiomatisation exists. We do the same for other signatures including one or both of disjoint union and subset complement, another partial binary operation we define. Domain-disjoint union is a partial binary operation on partial functions, returning the union if the arguments have disjoint domains and undefined otherwise. For each signature including one or both of domain-disjoint union and subset complement and optionally including composition, we consider the class of partial algebras isomorphic to a collection of partial functions closed under the operations. Again the classes prove to be axiomatisable, but not finitely axiomatisable, in first-order logic. We define the notion of pairwise combinability. For each of the previously considered signatures, we examine the class isomorphic to a partial algebra of sets/partial functions under an isomorphism mapping arbitrary suprema of pairwise combinable sets to the corresponding disjoint unions. We prove that for each case the class is not closed under elementary equivalence. However, when intersection is added to any of the signatures considered, the isomorphism class of the partial algebras of sets is finitely axiomatisable and in each case we give such an axiomatisation.

Abstract Hirsch and Hodkinson proved, for $3 \le m < \omega $ and any $k < \omega $ , that the class $SNr_m {\bf{CA}}_{m + k + 1} $ is strictly contained in $SNr_m {\bf{CA}}_{m + k} $ and if $k \ge 1$ then the former class cannot be defined by any finite set of first-order formulas, within the latter class. We generalize this result to the following algebras of m-ary relations for which the neat reduct operator $_m $ is meaningful: polyadic algebras with or without equality and substitution algebras. We also generalize this result to allow the case where m is an infinite ordinal, using quasipolyadic algebras in place of polyadic algebras (with or without equality).

Abstract In this article we establish the undecidability of representability and of finite representability as algebras of binary relations in a wide range of signatures. In particular, representability and finite representability are undecidable for Boolean monoids and lattice ordered monoids, while representability is undecidable for Jónsson's relation algebra. We also establish a number of undecidability results for representability as algebras of injective functions.

Abstract It is known that for all finite n ≥ 5, there are relation algebras with n-dimensional relational bases but no weak representations. We prove that conversely, there are finite weakly representable relation algebras with no n-dimensional relational bases. In symbols: neither of the classes RAn and wRRA contains the other.

The notion of warrant or justification is one of the central concepts in formal models of argumentation. The dialectical definition of warrant is expressed in terms of recursive defeat: an argument is warranted if each of its counter-arguments is itself defeated by a warranted counter-argument. However, few complexity results exist on checking whether an argument is warranted in the context of deductive models of argumentation, i.e. models where an argument is a deduction of a claim from a set of premises using some logic. We investigate the computational complexity of checking whether a claim is warranted in propositional argumentation under two natural definitions of warrant and show that it is PSPACE-complete in both cases.

Abstract A cylindric algebra atom structure is said to be strongly representable if all atomic cylindric algebras with that atom structure are representable. This is equivalent to saying that the full complex algebra of the atom structure is a representable cylindric algebra. We show that for any finite n ≥ 3, the class of all strongly representable n-dimensional cylindric algebra atom structures is not closed under ultraproducts and is therefore not elementary. Our proof is based on the following construction. From an arbitrary undirected, loop-free graph Γ, we construct an n-dimensional atom structure , and prove, for infinite Γ, that is a strongly representable cylindric algebra atom structure if and only if the chromatic number of Γ is infinite. A construction of Erdős shows that there are graphs Γk(k < ω) with infinite chromatic number, but having a non-principal ultraproduct ΠDΓk whose chromatic number is just two. It follows that is strongly representable (each k < ω) but is not.

We describe a method for generating accurate, compact, human understandable text classifiers. Text datasets are indexed using Apache Lucene and Genetic Programs are used to construct Lucene search queries. Genetic programs acquire fitness by producing queries that are effective binary classifiers for a particular category when evaluated against a set of training documents. We describe a set of functions and terminals and provide results from classification tasks.

Abstract We show, for any ordinalγ≥ 3, that the classℜaCAγis pseudo-elementary and has a recursively enumerable elementary theory. ScKdenotes the class of strong subalgebras of members of the classK. We devise games,Fn(3 ≤n≤ω),G, H, and show, for an atomic relation algebra with countably many atoms, that for 3 ≤n<ω. We use these games to show, forγ> 5 and any classKof relation algebras satisfying thatKis not closed under subalgebras and is not elementary. For infiniteγ, the inclusion ℜaCAγ⊂ScℜaCAγis strict. For infiniteγand for a countable relation algebra we show that has a complete representation if and only if is atomic and ∃ has a winning strategy inF(At( )) if and only if is atomic and ∈ScℜaCAγ.

Journal Article Peirce Algebras and Boolean Modules Get access R. Hirsch R. Hirsch Computer Science, University College of London, London, UK. Search for other works by this author on: Oxford Academic Google Scholar Journal of Logic and Computation, Volume 17, Issue 2, April 2007, Pages 255–283, https://doi.org/10.1093/logcom/exl037 Published: 03 January 2007 Article history Received: 18 May 2006 Published: 03 January 2007

Abstract We prove that everyn-modal logic betweenKnandS5nis undecidable, whenever n ≥ 3. We also show that each of these logics is non-finitely axiomatizable, lacks the product finite model property, and there is no algorithm deciding whether a finite frame validates the logic. These results answer several questions of Gabbay and Shehtman. The proofs combine the modal logic technique of Yankov–Fine frame formulas with algebraic logic results of Halmos, Johnson and Monk, and give a reduction of the (undecidable) representation problem of finite relation algebras.

Abstract We confirm a conjecture, about neat embeddings of cylindric algebras, made in 1969 by J. D. Monk, and a later conjecture by Maddux about relation algebras obtained from cylindric algebras. These results in algebraic logic have the following consequence for predicate logic: for every finite cardinal α ≥ 3 there is a logically valid sentence X, in a first-order language ℒ with equality and exactly one nonlogical binary relation symbol E, such that X contains only 3 variables (each of which may occur arbitrarily many times), X has a proof containing exactly α + 1 variables, but X has no proof containing only α variables. This solves a problem posed by Tarski and Givant in 1987.

Abstract We consider the problem of finding and classifying representations in algebraic logic. This is approached by letting two players build a representation using a game. Homogeneous and universal representations are characterized according to the outcome of certain games. The Lyndon conditions defining representable relation algebras (for the finite case) and a similar schema for cylindric algebras are derived. Finte relation algebras with homogeneous representations are characterized by first order formulas. Equivalence games are defined, and are used to establish whether an algebra is ω-categorical. We have a simple proof that the perfect extension of a representable relation algebra is completely representable. An important open problem from algebraic logic is addressed by devising another two-player game, and using it to derive equational axiomatisations for the classes of all representable relation algebras and representable cylindric algebras. Other instances of this approach are looked at, and include the step by step method.

Abstract A boolean algebra is shown to be completely representable if and only if it is atomic, whereas it is shown that neither the class of completely representable relation algebras nor the class of completely representable cylindric algebras of any fixed dimension (at least 3) are elementary.

Two complexity problems in algebraic logic are surveyed: the satisfaction problem and the network satisfaction problem. Various complexity results are collected here and some new ones are derived. Many examples are given. The network satisfaction problem for most cylindric algebras of dimension four or more is shown to be intractable. Complexity is tied-in with the expressivity of a relation algebra. Expressivity and complexity are analysed in the context of homogeneous representations. The model-theoretic notion of interpretation is used to generalize known complexity results to a range of other algebraic logics. In particular a number of relation algebras arc shown to have intractable network satisfaction problems.

The Allen and Koomen planner is intractable in two ways: the Allen interval algebra is an intractable temporal reasoner, and the collapsing problem introduces a large branching factor in the search space for a solution plan. We define independence and dependence for networks to address both problems. Independence is used to find a decomposition of an interval network, and dependence is used to focus search when faced with the collapsing problem.