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 algebras were invented by Tarski and his collaborators in the middle of the 20th century. The concept of integrality arose naturally early in the history of the subject, as did various constructions of finite integral relation algebras. Later the concept of finite-dimensionality was introduced for classifying nonrepresentable relation algebras. This concept is closely connected to the number of variables used in proofs in first-order logic. Some results on these topics are presented in chronological order.

We develop a variant of Least Fixed Point logic based on First Orderlogic with a relaxed version of guarded quantification. We develop aGame Theoretic Semantics of this logic, and find that under reasonableconditions, guarding quantification does not reduce the expressibilityof Least Fixed Point logic. But we also find that the guarded version ofa least fixed point algorithm may have a greater time complexity thanthe unguarded version, by a linear factor.

We prove that algebras of binary relations whose similarity type includes intersection, union, and one of the residuals of relation composition form a nonfinitely axiomatizable quasivariety and that the equational theory is not finitely based. We apply this result to the problem of the completeness of the positive fragment of relevance logic with respect to binary relations.

We provide complete classifications of algebras of partial maps for a significant swathe of combinations of operations not previously classified. Our focus is the many subsidiary operations that arise in recent considerations of the ‘override’ and ‘update’ operations arising in specification languages. These other operations turn out to have an older pedigree: domain restriction, set subtraction and intersection. All signatures considered include domain restriction, at least as a term. Combinations of the operations are classified and given complete axiomatizations with and (...) without the presence of functional composition. Each classification is achieved by way of providing a concrete representation of the corresponding abstract algebras as partial maps acting on special kinds of filters determined with respect to various induced orders. In contrast to many negative results in the broader area, all of the considered combinations lead to finite axiomatizations. (shrink)

This paper is based on tutorials on 'Logic and Games' at the 7th Asian Logic Conference in Hsi-Tou, Taiwan, 1999, and until 2002 in Siena, Stuttgart, Trento, Udine, and Utrecht. We present logic games as a topic per se, giving models for dynamic interaction between agents. First, we survey some basic logic games. Then we show how their common properties raise general issues of game structure and 'game logics'. Next, we review logic games in the light of general game logic. (...) Finally, we discuss more 'realistic' influences from game theory into logic games, including players' preferences, and imperfect information. (shrink)