UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Some Undecidable Problems on Representability as Binary Relations

Hirsch, R; Jackson, M; (2012) Some Undecidable Problems on Representability as Binary Relations. The Journal of Symbolic Logic , 77 (4) pp. 1211-1244. Green open access

[thumbnail of InjUndecidJSLc.pdf]
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
Downloads since deposit
171Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item