Document Open Access Logo

Non Axiomatisability of Positive Relation Algebras with Constants, via Graph Homomorphisms

Authors Amina Doumane, Damien Pous

PDF
Thumbnail PDF

File

LIPIcs.CONCUR.2020.29.pdf
  • Filesize: 0.54 MB
  • 16 pages

Document Identifiers

Author Details

Amina Doumane
  • Université Lyon, CNRS, ENS de Lyon, UCB Lyon 1, LIP, Lyon, France
Damien Pous
  • Université Lyon, CNRS, ENS de Lyon, UCB Lyon 1, LIP, Lyon, France

Funding

This work has been funded by the European Research Council (ERC-StG CoVeCe 678157) and the French National Research Agency (ANR-10-LABX-0070 ANR-11-IDEX-0007).

Cite As Get BibTex

Amina Doumane and Damien Pous. Non Axiomatisability of Positive Relation Algebras with Constants, via Graph Homomorphisms. In 31st International Conference on Concurrency Theory (CONCUR 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 171, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.CONCUR.2020.29

Abstract

We study the equational theories of composition and intersection on binary relations, with or without their associated neutral elements (identity and full relation). Without these constants, the equational theory coincides with that of semilattice-ordered semigroups. We show that the equational theory is no longer finitely based when adding one or the other constant, refuting a conjecture from the literature. Our proofs exploit a characterisation in terms of graphs and homomorphisms, which we show how to adapt in order to capture standard equational theories over the considered signatures.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Discrete mathematics
Keywords
  • Relation algebra
  • graph homomorphisms
  • (in)equational theories

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. H. Andréka and D.A. Bredikhin. The equational theory of union-free algebras of relations. Algebra Universalis, 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. Bredihin and B. M. Schein. Representations of ordered semigroups and lattices by binary relations. Colloquium Mathematicae, 39(1):1-12, 1978. URL: http://eudml.org/doc/266458.
  4. 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.
  5. Paul Brunet. The equational theory of algebras of languages. Talk at RAMiCS, Lyon, May 2017 (Special session on mechanised reasoning), 2017. Google Scholar
  6. Paul Brunet and Damien Pous. Petri automata for Kleene allegories. In LICS, pages 68-79. ACM, 2015. URL: https://doi.org/10.1109/LICS.2015.17.
  7. Chandra Chekuri and Anand Rajaraman. Conjunctive query containment revisited. Theoretical Computer Science, 239(2):211-229, 2000. URL: https://doi.org/10.1016/S0304-3975(99)00220-0.
  8. R. Diestel. Graph Theory. Graduate Texts in Mathematics. Springer, 2005. Google Scholar
  9. Amina Doumane and Damien Pous. Completeness for identity-free Kleene lattices. In CONCUR, volume 118 of LIPIcs, pages 18:1-18:17. Schloss Dagstuhl, 2018. URL: https://doi.org/10.4230/LIPIcs.CONCUR.2018.18.
  10. Amina Doumane and Damien Pous. Full version of this paper, with appendices, 2020. URL: https://hal.archives-ouvertes.fr/hal-02870687.
  11. Z. Ésik and L. Bernátsky. Equational properties of Kleene algebras of relations with conversion. Theoretical Computer Science, 137(2):237-251, 1995. URL: https://doi.org/10.1016/0304-3975(94)00041-G.
  12. Eugene C. Freuder. Complexity of k-tree structured constraint satisfaction problems. In NCAI, pages 4-9. AAAI Press / The MIT Press, 1990. URL: http://www.aaai.org/Library/AAAI/1990/aaai90-001.php.
  13. P. Freyd and A. Scedrov. Categories, Allegories. North Holland, 1990. Google Scholar
  14. Jay L. Gischer. The equational theory of pomsets. Theoretical Computer Science, 61(2):199-224, 1988. URL: https://doi.org/10.1016/0304-3975(88)90124-7.
  15. J. Grabowski. On partial languages. Fundamenta Informaticae, 4:427-498, 1981. Google Scholar
  16. Martin Grohe. The complexity of homomorphism and constraint satisfaction problems seen from the other side. Journal of the ACM, 54(1):1:1-1:24, 2007. URL: https://doi.org/10.1145/1206035.1206036.
  17. T. Hoare, B. Möller, G. Struth, and I. Wehrman. Concurrent Kleene algebra and its foundations. Journal of Logic and Algebraic Programming, 80(6):266-296, 2011. Google Scholar
  18. 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.
  19. Roger Maddux. Relation Algebras. Elsevier, 2006. Google Scholar
  20. 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.
  21. Donald Monk. On representable relation algebras. The Michigan mathematical journal, 31(3):207-210, 1964. URL: https://doi.org/10.1307/mmj/1028999131.
  22. 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.
  23. Damien Pous and Valeria Vignudelli. Allegories: decidability and graph homomorphisms. In LiCS, pages 829-838. ACM, 2018. URL: https://doi.org/10.1145/3209108.3209172.
  24. V. Pratt. Origins of the calculus of binary relations. In LICS, pages 248-254. IEEE Computer Society Press, 1992. Google Scholar
  25. A. Tarski. On the calculus of relations. J. of Symbolic Logic, 6(3):73-89, 1941. Google Scholar
  26. A. Tarski and S. Givant. A Formalization of Set Theory without Variables, volume 41 of Colloquium Publications. American Mathematical Society, 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 About DROPS Imprint Privacy Contact