Abstract
A binary relation defined on a poset is a weakening relation if the partial order acts as a both-sided compositional identity. This is motivated by the weakening rule in sequent calculi and closely related to models of relevance logic. For a fixed poset the collection of weakening relations is a subreduct of the full relation algebra on the underlying set of the poset. We present a two-player game for the class of representable weakening relation algebras akin to that for the class of representable relation algebras. This enables us to define classes of abstract weakening relation algebras that approximate the quasivariety of representable weakening relation algebras. We give explicit finite axiomatisations for some of these classes. We define the class of diagonally representable weakening relation algebras and prove that it is a discriminator variety. We also provide explicit representations for several small weakening relation algebras.
This work was supported by the Engineering and Physical Sciences Research Council EP/S021566/1.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bimbó, K., Dunn, J.M., Maddux, R.D.: Relevance logics and relation algebras. Rev. Symb. Log. 2(1), 102–131 (2009). https://doi.org/10.1017/S1755020309090145
Galatos, N., Jipsen, P.: Distributive residuated frames and generalized bunched implication algebras. Algebra Univers. 78(3), 303–336 (2017). https://doi.org/10.1007/s00012-017-0456-x
Galatos, N., Jipsen, P.: The structure of generalized BI-algebras and weakening relation algebras. Algebra Univers. 81(3), 1–35 (2020). https://doi.org/10.1007/s00012-020-00663-9
Galatos, N., Jipsen, P.: Weakening relation algebras and FL\(^2\)-algebras. In: Fahrenberg, U., Jipsen, P., Winter, M. (eds.) RAMiCS 2020. LNCS, vol. 12062, pp. 117–133. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-43520-2_8
Givant, S.: Advanced Topics in Relation Algebras, vol. 2. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-319-65945-9
Givant, S.: Introduction to Relation Algebras, vol. 1. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-319-65235-1
Hirsch, R.: Relation algebras of intervals. Artif. Intell. 83(2), 267–295 (1996). https://doi.org/10.1016/0004-3702(95)00042-9
Hirsch, R., Hodkinson, I.: Relation Algebras by Games. Elsevier, Amsterdam (2002)
Jipsen, P.: Relation algebras, idempotent semirings and generalized bunched implication algebras. In: Höfner, P., Pous, D., Struth, G. (eds.) RAMICS 2017. LNCS, vol. 10226, pp. 144–158. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-57418-9_9
Kurz, A., Velebil, J.: Relation lifting, a survey. J. Log. Algebraic Methods Program. 85(4), 475–499 (2016)
Maddux, R.: Relation Algebras, vol. 13. Elsevier, Amsterdam (2006)
Maddux, R.: Some varieties containing relation algebras. Trans. Amer. Math. Soc. 272(2), 501–526 (1982). https://doi.org/10.2307/1998710
Maddux, R.: A sequent calculus for relation algebras. Ann. Pure Appl. Log. 25(1), 73–101 (1983). https://doi.org/10.1016/0168-0072(83)90055-6
Maddux, R.D.: Relevance logic and the calculus of relations. Rev. Symb. Log. 3(1), 41–70 (2010). https://doi.org/10.1017/S1755020309990293
Maddux, R.D.: Tarskian classical relevant logic. In: Düntsch, I., Mares, E. (eds.) Alasdair Urquhart on Nonclassical and Algebraic Logic and Complexity of Proofs. OCL, vol. 22, pp. 67–161. Springer, Cham (2022). https://doi.org/10.1007/978-3-030-71430-7_3
McCune, W.: Prover9 and Mace4 (2005–2010). www.cs.unm.edu/ mccune/prover9/
Monk, D.: On representable relation algebras. Michigan Math. J. 11, 207–210 (1964). projecteuclid.org/euclid.mmj/1028999131
Reynolds, J.C.: Separation logic: a logic for shared mutable data structures. In: Proceedings 17th Annual IEEE Symposium on Logic in Computer Science, pp. 55–74. IEEE (2002)
Smyth, M.: Stable compactification i. J. Lond. Math. Soc. 2(2), 321–340 (1992)
Stell, J.G.: Relations on hypergraphs. In: Kahl, W., Griffin, T.G. (eds.) RAMICS 2012. LNCS, vol. 7560, pp. 326–341. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33314-9_22
Stell, J.G.: Symmetric Heyting relation algebras with applications to hypergraphs. J. Log. Algebr. Methods Program. 84(3), 440–455 (2015). https://doi.org/10.1016/j.jlamp.2014.12.001
Tarski, A.: Contributions to the theory of models. J. Symb. Log. 21(4) (1956)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Jipsen, P., Šemrl, J. (2023). Representable and Diagonally Representable Weakening Relation Algebras. In: Glück, R., Santocanale, L., Winter, M. (eds) Relational and Algebraic Methods in Computer Science. RAMiCS 2023. Lecture Notes in Computer Science, vol 13896. Springer, Cham. https://doi.org/10.1007/978-3-031-28083-2_9
Download citation
DOI: https://doi.org/10.1007/978-3-031-28083-2_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-28082-5
Online ISBN: 978-3-031-28083-2
eBook Packages: Computer ScienceComputer Science (R0)