
eBook ISBN: | 978-1-4704-0189-4 |
Product Code: | MEMO/126/604.E |
List Price: | $48.00 |
MAA Member Price: | $43.20 |
AMS Member Price: | $28.80 |

eBook ISBN: | 978-1-4704-0189-4 |
Product Code: | MEMO/126/604.E |
List Price: | $48.00 |
MAA Member Price: | $43.20 |
AMS Member Price: | $28.80 |
-
Book DetailsMemoirs of the American Mathematical SocietyVolume: 126; 1997; 126 ppMSC: Primary 03; Secondary 08
This work presents a systematic study of decision problems for equational theories of algebras of binary relations (relation algebras). For example, an easily applicable but deep method, based on von Neumann's coordinatization theorem, is developed for establishing undecidability results. The method is used to solve several outstanding problems posed by Tarski. In addition, the complexity of intervals of equational theories of relation algebras with respect to questions of decidability is investigated. Using ideas that go back to Jónsson and Lyndon, the authors show that such intervals can have the same complexity as the lattice of subsets of the set of the natural numbers. Finally, some new and quite interesting examples of decidable equational theories are given.
The methods developed in the monograph show promise of broad applicability. They provide researchers in algebra and logic with a new arsenal of techniques for resolving decision questions in various domains of algebraic logic.
ReadershipGraduate students, research mathematicians and computer scientists interested in questions of computability in algebra, logic and computer science.
-
Table of Contents
-
Chapters
-
I. Preliminaries
-
II. Undecidability
-
III. A lattice embedding that preserves decidability and undecidability
-
IV. A finitely generated, infinite, simple relation algebra with a decidable equational theory
-
-
RequestsReview Copy – for publishers of book reviewsPermission – for use of book, eBook, or Journal contentAccessibility – to request an alternate format of an AMS title
- Book Details
- Table of Contents
- Requests
This work presents a systematic study of decision problems for equational theories of algebras of binary relations (relation algebras). For example, an easily applicable but deep method, based on von Neumann's coordinatization theorem, is developed for establishing undecidability results. The method is used to solve several outstanding problems posed by Tarski. In addition, the complexity of intervals of equational theories of relation algebras with respect to questions of decidability is investigated. Using ideas that go back to Jónsson and Lyndon, the authors show that such intervals can have the same complexity as the lattice of subsets of the set of the natural numbers. Finally, some new and quite interesting examples of decidable equational theories are given.
The methods developed in the monograph show promise of broad applicability. They provide researchers in algebra and logic with a new arsenal of techniques for resolving decision questions in various domains of algebraic logic.
Graduate students, research mathematicians and computer scientists interested in questions of computability in algebra, logic and computer science.
-
Chapters
-
I. Preliminaries
-
II. Undecidability
-
III. A lattice embedding that preserves decidability and undecidability
-
IV. A finitely generated, infinite, simple relation algebra with a decidable equational theory