Item Successfully Added to Cart
An error was encountered while trying to add the item to the cart. Please try again.
OK
Please make all selections above before adding to cart
OK
Share this page via the icons above, or by copying the link below:
Copy To Clipboard
Successfully Copied!
Decision Problems for Equational Theories of Relation Algebras
 
Hajnal Andréka Mathematical Institute, Budapest, Hungary
Steven Givant Mills College, Oakland, CA
István Németi Mathematical Institute, Budapest, Hungary
Decision Problems for Equational Theories of Relation Algebras
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
Decision Problems for Equational Theories of Relation Algebras
Click above image for expanded view
Decision Problems for Equational Theories of Relation Algebras
Hajnal Andréka Mathematical Institute, Budapest, Hungary
Steven Givant Mills College, Oakland, CA
István Németi Mathematical Institute, Budapest, Hungary
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 Details
     
     
    Memoirs of the American Mathematical Society
    Volume: 1261997; 126 pp
    MSC: 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.

    Readership

    Graduate 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
  • Requests
     
     
    Review Copy – for publishers of book reviews
    Permission – for use of book, eBook, or Journal content
    Accessibility – to request an alternate format of an AMS title
Volume: 1261997; 126 pp
MSC: 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.

Readership

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
Review Copy – for publishers of book reviews
Permission – for use of book, eBook, or Journal content
Accessibility – to request an alternate format of an AMS title
Please select which format for which you are requesting permissions.