LIPIcs.MFCS.2021.1.pdf
- Filesize: 268 kB
- 1 pages
Document
Non-Axiomatizability of the Equational Theories of Positive Relation Algebras (Invited Talk)
Author
-
Part of:
Volume:
46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Mathematical Foundations of Computer Science (MFCS) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-08-18
Cite As Get BibTex
Amina Doumane. Non-Axiomatizability of the Equational Theories of Positive Relation Algebras (Invited Talk). In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.MFCS.2021.1
Abstract
In the literature, there are two ways to show that the equational theory of relations over a given signature is not finitely axiomatizable. The first-one is based on games and a construction called Rainbow construction. This method is very technical but it shows a strong result: the equational theory cannot be axiomatized by any finite set of first-order formulas. There is another method, based on a graph characterization of the equational theory of relations, which is easier to get and to understand, but proves a weaker result: the equational theory cannot be axiomatized by any finite set of equations. In this presentation, I will show how to complete the second technique to get the stronger result of non-axiomatizability by first-order formulas.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Discrete mathematics
Keywords
- Relation algebra
- Graph homomorphism
- Equational theories
- First-order logic
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads