Undecidability of representability as binary relations

Journal of Symbolic Logic 77 (4):1211-1244 (2012)
  Copy   BIBTEX


In this article we establish the undecidability of representability and of finite representability as algebras of binary relations in a wide range of signatures. In particular, representability and finite representability are undecidable for Boolean monoids and lattice ordered monoids, while representability is undecidable for Jónsson's relation algebra. We also establish a number of undecidability results for representability as algebras of injective functions



    Upload a copy of this work     Papers currently archived: 91,139

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Two variable first-order logic over ordered domains.Martin Otto - 2001 - Journal of Symbolic Logic 66 (2):685-702.
Groups and algebras of binary relations.Steven Givant & Hajnal Andréka - 2002 - Bulletin of Symbolic Logic 8 (1):38-64.
Undecidable theories.Alfred Tarski - 1953 - Amsterdam,: North-Holland Pub. Co.. Edited by Andrzej Mostowski & Raphael M. Robinson.
Dynamic relation logic is the logic of DPL-Relations.Albert Visser - 1997 - Journal of Logic, Language and Information 6 (4):441-452.
The undecidability of the DA-Unification problem.J. Siekmann & P. Szabó - 1989 - Journal of Symbolic Logic 54 (2):402 - 414.
Bicartesian coherence.Kosta Došen & Zoran Petrić - 2002 - Studia Logica 71 (3):331 - 353.


Added to PP

23 (#637,895)

6 months
5 (#510,007)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Restriction in Program Algebra.Marcel Jackson & Tim Stokes - 2023 - Logic Journal of the IGPL 31 (5):926-960.

Add more citations