Document Open Access Logo

Graph Characterization of the Universal Theory of Relations

Author Amina Doumane

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.41.pdf
  • Filesize: 0.68 MB
  • 15 pages

Document Identifiers

Author Details

Amina Doumane
  • CNRS, ENS Lyon, France

Acknowledgements

I am deeply grateful to Denis Kuperberg and Damien Pous for their great help.

Cite AsGet BibTex

Amina Doumane. Graph Characterization of the Universal Theory of Relations. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 41:1-41:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.MFCS.2021.41

Abstract

The equational theory of relations can be characterized using graphs and homomorphisms. This result, found independently by Freyd and Scedrov and by Andréka and Bredikhin, shows that the equational theory of relations is decidable. In this paper, we extend this characterization to the whole universal first-order theory of relations. Using our characterization, we show that the positive universal fragment is also decidable.

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)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. H. Andréka and D.A. Bredikhin. The equational theory of union-free algebras of relations. au, 33(4):516-532, 1995. URL: https://doi.org/10.1007/BF01225472.
  2. Hajnal Andréka and Szabolcs Mikulás. Axiomatizability of positive algebras of binary relations. Algebra universalis, 66(7), 2011. An erratum appears at http://www.dcs.bbk.ac.uk/~szabolcs/AM-AU-err6.pdf. URL: https://doi.org/10.1007/s00012-011-0142-3.
  3. D. A. Bredikhin. The equational theory of relation algebras with positive operations. Izv. Vyssh. Uchebn. Zaved. Mat., 37(3):23-30, 1993. In Russian. URL: http://mi.mathnet.ru/ivm4374.
  4. Paul Brunet and Damien Pous. Petri automata for kleene allegories. In 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015, Kyoto, Japan, July 6-10, 2015, pages 68-79. IEEE Computer Society, 2015. URL: https://doi.org/10.1109/LICS.2015.17.
  5. Ashok K. Chandra and Philip M. Merlin. Optimal implementation of conjunctive queries in relational data bases. In John E. Hopcroft, Emily P. Friedman, and Michael A. Harrison, editors, Proceedings of the 9th Annual ACM Symposium on Theory of Computing, May 4-6, 1977, Boulder, Colorado, USA, pages 77-90. ACM, 1977. URL: https://doi.org/10.1145/800105.803397.
  6. Martin D. Davis. Computability and Unsolvability. McGraw-Hill Series in Information Processing and Computers. McGraw-Hill, 1958. Google Scholar
  7. P. Freyd and A. Scedrov. Categories, Allegories. nh, 1990. Google Scholar
  8. Wilfrid Hodges. A Shorter Model Theory. Cambridge University Press, USA, 1997. Google Scholar
  9. Ian Hodkinson and Szabolcs Mikulás. Axiomatizability of reducts of algebras of relations. Algebra Universalis, 43:127-156, 2000. URL: https://doi.org/10.1007/s000120050150.
  10. Roger Maddux. Relation Algebras. Elsevier, 2006. Google Scholar
  11. Szabolcs Mikulás. Axiomatizability of algebras of binary relations. In Classical and New Paradigms of Computation and their Complexity Hierarchies, pages 187-205. Springer Netherlands, 2004. URL: https://doi.org/10.1007/978-1-4020-2776-5_11.
  12. Donald Monk. On representable relation algebras. The Michigan mathematical journal, 31(3):207-210, 1964. URL: https://doi.org/10.1307/mmj/1028999131.
  13. Yoshiki Nakamura. Partial derivatives on graphs for kleene allegories. In Lics, pages 1-12. ieee, 2017. URL: https://doi.org/10.1109/LICS.2017.8005132.
  14. A. Tarski. On the calculus of relations. J. of Symbolic Logic, 6(3):73-89, 1941. Google Scholar
  15. A. Tarski and S. Givant. A Formalization of Set Theory without Variables, volume 41 of Colloquium Publications. ams, Providence, Rhode Island, 1987. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact