Representability is not decidable for finite relation algebras
Robin Hirsch, Ian Hodkinson · Transactions of the American Mathematical Society · 1999
We prove that there is no algorithm that decides whether a finite relation algebra is representable. Representability of a finite relation algebra A \mathcal A is determined by playing a certain two player game G ( A ) G({\mathcal A}) over ‘atomic A \mathcal A -networks’. It can be shown that the second player in this game has a winning strategy if and only if A \mathcal A is representable. Let τ \tau be a finite set of square tiles, where each edge of each tile has a colour. Suppose τ \tau includes a special tile whose four edges are all the same colour, a colour not used by any other tile. The tiling problem we use is this: is it the case that for each tile T ∈ τ T \in \tau there is a tiling of the plane Z × Z {\mathbb Z}\times {\mathbb Z} using only tiles from τ \tau in which edge colours of adjacent tiles match and with T T placed at ( 0 , 0 ) (0,0) ? It is not hard to show that this problem is undecidable. From an instance of this tiling problem τ \tau , we construct a finite relation algebra R A ( τ