Relation Algebras Can Tile
Maarten Marx

Abstract:
Abstract Undecidability of the equational theory of the class RA of 
relation algebras can easily be proved using the undecidability of 
the wordproblem for semigroups. With some effort and ingenuity, one
can push this proof through for the larger class SA. We provide 
another "cause" for undecidability which works for even larger classes 
than SA. The reason is that we can encode the tiling problem. In doing 
so we will meet very simple BAO-varieties with undecidable equational 
theories which might be useful in other undecidability proofs.

Our work is part of the research project which tries to establish the 
border between undecidability and decidability in relational type 
algebras, cf (N'emeti, 1987), (Maddux, 1994), (Andr'eka et al., 1995) 
and the references therein, (Marx, 1995). The ultimate goal of this
 research is to come up with versions of relational algebra which are 
still suitable for modern dynamic applications but whose equational 
theory is decidable or even tractable.

To appear in `Information Science'.