Imperial College London
Portrait Picture

Emeritus ProfessorIanHodkinson

Faculty of Engineering, Department of Computing

Emeritus Professor of Logic and Computation
 
 
 
//

Contact

 

i.hodkinson Website

 
 
//

Location

 

noneHuxley BuildingSouth Kensington Campus

//

Summary

 

Publications

Citation

BibTex format

@inbook{Hirsch:2021:10.1007/978-3-030-64187-0_11,
author = {Hirsch, R and Hodkinson, I and Jackson, M},
booktitle = {Outstanding Contributions to Logic},
doi = {10.1007/978-3-030-64187-0_11},
pages = {267--287},
title = {Undecidability of Algebras of Binary Relations},
url = {http://dx.doi.org/10.1007/978-3-030-64187-0_11},
year = {2021}
}
Download

RIS format (EndNote, RefMan)

TY  - CHAP
AB  - Let S be a signature of operations and relations definable in relation algebra (e.g. converse, composition, containment, union, identity, etc.), let R(S) be the class of all S-structures isomorphic to concrete algebras of binary relations with concrete interpretations for symbols in S, and let F(S) be the class of S-structures isomorphic to concrete algebras of binary relations over a finite base. To prove that membership of R(S) or F(S) for finite S-structures is undecidable, we reduce from a known undecidable problem—here we use the tiling problem, the partial group embedding problem and the partial group finite embedding problem to prove undecidability of finite membership of R(S) or F(S) for various signatures S. It follows that the equational theory of R(S) is undecidable whenever S includes the boolean operators and composition. We give an exposition of the reduction from the tiling problem and the reduction from the group embedding problem, and summarize what we know about the undecidability of finite membership of R(S) and of F(S) for different signatures S.
AU  - Hirsch,R
AU  - Hodkinson,I
AU  - Jackson,M
DO  - 10.1007/978-3-030-64187-0_11
EP  - 287
PY  - 2021///
SP  - 267
TI  - Undecidability of Algebras of Binary Relations
T1  - Outstanding Contributions to Logic
UR  - http://dx.doi.org/10.1007/978-3-030-64187-0_11
ER  -
Download