Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Representability is not decidable
for finite relation algebras

Authors: Robin Hirsch and Ian Hodkinson
Journal: Trans. Amer. Math. Soc. 353 (2001), 1403-1425
MSC (1991): Primary 03G15; Secondary 03G05, 06E25, 03D35
Published electronically: April 23, 1999
MathSciNet review: 1806735
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We prove that there is no algorithm that decides whether a finite relation algebra is representable.

Representability of a finite relation algebra $\mathcal A$ is determined by playing a certain two player game $G({\mathcal A})$ over `atomic $\mathcal A$-networks'. It can be shown that the second player in this game has a winning strategy if and only if $\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 \in \tau$ there is a tiling of the plane ${\mathbb Z}\times {\mathbb Z}$ using only tiles from $\tau$ in which edge colours of adjacent tiles match and with $T$ placed at $(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 $RA(\tau)$ and show that the second player has a winning strategy in $G(RA(\tau))$ if and only if $\tau$ is a yes-instance. This reduces the tiling problem to the representation problem and proves the latter's undecidability.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (1991): 03G15, 03G05, 06E25, 03D35

Retrieve articles in all journals with MSC (1991): 03G15, 03G05, 06E25, 03D35

Additional Information

Robin Hirsch
Affiliation: Department of Computer Science, University College, Gower Street, London WC1E 6BT, U.K.

Ian Hodkinson
Affiliation: Department of Computing, Imperial College, Queen’s Gate, London SW7 2BZ, U.K.

Keywords: Relation algebra, representation, undecidability, tiling problem, games, algebraic logic
Received by editor(s): April 2, 1997
Received by editor(s) in revised form: November 11, 1997
Published electronically: April 23, 1999
Additional Notes: Research of the second author was partially supported by UK EPSRC grant GR/K54946. Many thanks to Peter Jipsen, Maarten Marx, Szabolcs Mikulás, Mark Reynolds, Yde Venema and the referee for useful comments and for pointing out serious errors in early drafts of this paper.
Article copyright: © Copyright 1999 American Mathematical Society