Hirsch, R;
Jackson, M;
(2012)
Some Undecidable Problems on Representability as Binary Relations.
The Journal of Symbolic Logic
, 77
(4)
pp. 1211-1244.
![[thumbnail of InjUndecidJSLc.pdf]](https://discovery.ucl.ac.uk/style/images/fileicons/application_pdf.png) Preview |
PDF
InjUndecidJSLc.pdf Available under License : See the attached licence file. Download (511kB) |
Abstract
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 onsson's relation algebra. We also establish a number of undecidability results for representability as algebras of injective functions.
| Type: | Article |
|---|---|
| Title: | Some Undecidable Problems on Representability as Binary Relations |
| Open access status: | An open access version is available from UCL Discovery |
| Publisher version: | http://www.aslonline.org/journals-journal.html |
| Language: | English |
| Keywords: | Undecidability, Algebras of relations, Binary relation, Representation |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/1330692 |
Archive Staff Only
 |
View Item |
