Tutorial on Foundations of Relations and Kleene Algebra

Peter Jipsen, Chapman University, USA

This tutorial aims to provide an up-to-date overview of relation algebras and Kleene algebras that will allow participants to follow the theoretical details of many of the subsequent research talks.

Starting with binary relations, partially ordered sets, (semi)lattices, Boolean algebras, monoids, categories, groups, semirings, residuation and iteration, we consider relation algebras and Kleene algebras (with tests) in a common framework and give a host of motivating examples.

Subsequent topics (may) include:

  • Duality of atom structures and complex algebras
  • Representability of relation algebras
  • Computing finite nonisomorphic models
  • Varieties of relation and Kleene algebras
  • Undecidable varieties of relation algebras
  • Heterogeneous and categorical approaches
  • Automata and matrices
  • Equational decidability of Kleene algebras (with tests)
  • A primer on algebraic logic and proof theoretic methods
  • Introduction to some generalizations:
    • nonassociative relation algebras
    • sequential algebras
    • action algebras and action lattices
  • Some applications in computing

Throughout we touch upon open problems and interesting research directions, with the hope of tapping the collective reasoning power of the participants to make some progress in these fields.

Last updated 21 Apr 2006.