zbMATH — the first resource for mathematics

Free Kleene algebras with domain. (English) Zbl 07271813
Summary: First we identify the free algebras of the class of algebras of binary relations equipped with the composition and domain operations. Elements of the free algebras are pointed labelled finite rooted trees. Then we extend to the analogous case when the signature includes all the Kleene algebra with domain operations; that is, we add union and reflexive transitive closure to the signature. In this second case, elements of the free algebras are ‘regular’ sets of the trees of the first case. As a corollary, the axioms of domain semirings provide a finite quasiequational axiomatisation of the equational theory of algebras of binary relations for the intermediate signature of composition, union, and domain. Next we note that our regular sets of trees are not closed under complement, but prove that they are closed under intersection. Finally, we prove that under relational semantics the equational validities of Kleene algebras with domain form a decidable set.
08B20 Free algebras
08A70 Applications of universal algebra in computer science
PDF BibTeX Cite
Full Text: DOI
[1] Benedikt, Michael; Koch, Christoph, XPath leashed, ACM Comput. Surv., 41, 3:1-3:54 (2009)
[2] Bloom, Stephen L.; Ésik, Zoltán; Stefanescu, Gheorghe, Notes on equational theories of relations, Algebra Univers., 33, 1, 98-126 (1995) · Zbl 0834.08004
[3] Burris, Stanley; Sankappanavar, Hanamantagouda P., A Course in Universal Algebra, Graduate Texts in Mathematics (2011), Springer · Zbl 0478.08001
[4] Desharnais, Jules; Möller, Bernhard; Struth, Georg, Kleene algebra with domain, ACM Trans. Comput. Log., 7, 4, 798-833 (2006) · Zbl 1367.68205
[5] Desharnais, Jules; Struth, Georg, Domain axioms for a family of near-semirings, (Meseguer, José; Roşu, Grigore, 12th International Conference on Algebraic Methodology and Software Technology. 12th International Conference on Algebraic Methodology and Software Technology, Lecture Notes in Computer Science, vol. 5140 (2008), Springer), 330-345 · Zbl 1170.68514
[6] Desharnais, Jules; Struth, Georg, Internal axioms for domain semirings, Sci. Comput. Program., 76, 3, 181-203 (2011) · Zbl 1211.68242
[7] Eilenberg, Samuel, Automata, Languages, and Machines (1974), Academic Press: Academic Press Orlando, Florida, USA · Zbl 0317.94045
[8] Fischer, Michael J.; Ladner, Richard E., Propositional dynamic logic of regular programs, J. Comput. Syst. Sci., 18, 2, 194-211 (1979) · Zbl 0408.03014
[9] Fountain, John, Free right type a semigroups, Glasg. Math. J., 33, 2, 135-148 (1991) · Zbl 0737.20032
[10] Fountain, John; Gomes, Gracinda M. S.; Gould, Victoria, The free ample monoid, Int. J. Algebra Comput., 19, 04, 527-554 (2009) · Zbl 1192.20041
[11] Gécseg, Ferenc; Steinby, Magnus, Tree languages, (Rozenberg, G.; Salomaa, A., Handbook of Formal Languages, vol. 3 (1997), Springer), 1-68
[12] Gehrke, Mai, Stone duality, topological algebra, and recognition, J. Pure Appl. Algebra, 220, 7, 2711-2747 (2016) · Zbl 1339.06012
[13] Gehrke, Mai; Grigorieff, Serge; Pin, Jean-Éric, Duality and equational theory of regular languages, (International Colloquium on Automata, Languages, and Programming (2008), Springer), 246-257 · Zbl 1165.68049
[14] Hellings, Jelle; Gyssens, Marc; Wu, Yuqing; Van Gucht, Dirk; Van den Bussche, Jan; Vansummeren, Stijn; Fletcher, George H. L., Comparing the expressiveness of downward fragments of the relation algebra with transitive closure on trees, Inf. Sci., 89, Article 101467 pp. (2020)
[15] Hellings, Jelle; Gyssens, Marc; Wu, Yuqing; Van Gucht, Dirk; Van den Bussche, Jan; Vansummeren, Stijn; Fletcher, George H. L., Relative expressive power of downward fragments of navigational query languages on trees and chains, (Proceedings of the 15th Symposium on Database Programming Languages (2015), ACM), 59-68
[16] Hirsch, Robin; Hodkinson, Ian, Relation Algebras by Games, Studies in Logic and the Foundations of Mathematics, vol. 147 (2002), North-Holland · Zbl 1018.03002
[17] Hirsch, Robin; Mikulás, Szabolcs, Axiomatizability of representable domain algebras, J. Log. Algebraic Program., 80, 2, 75-91 (2011) · Zbl 1207.68207
[18] Hollenberg, Marco, An equational axiomatization of dynamic negation and relational composition, J. Log. Lang. Inf., 6, 4, 381-401 (1997) · Zbl 0882.03065
[19] Jipsen, Peter; Struth, Georg, The structure of the one-generated free domain semiring, (Berghammer, Rudolf; Möller, Bernhard; Struth, Georg, Relations and Kleene Algebra in Computer Science. Relations and Kleene Algebra in Computer Science, Berlin, Heidelberg (2008), Springer), 234-242 · Zbl 1140.68041
[20] Kozen, Dexter, A completeness theorem for Kleene algebras and the algebra of regular events, Inf. Comput., 110, 2, 366-390 (1994) · Zbl 0806.68082
[21] Kozen, Dexter, Kleene algebra with tests, ACM Trans. Program. Lang. Syst., 19, 3, 427-443 (1997) · Zbl 0882.03064
[22] Libkin, Leonid; Martens, Wim; Vrgoč, Domagoj, Querying graph databases with XPath, (Proceedings of the 16th International Conference on Database Theory (2013), ACM), 129-140
[23] Łoś, Jerzy, Quelques remarques, théorèmes et problèmes sur les classes définissables d’algèbres, (Skolem, Thoralf; Hasenjaeger, Gisbert; Kreisel, Georg; Robinson, Abraham; Wang, Hao; Henkin, Leon; Łoś, Jerzy, Mathematical Interpretation of Formal Systems. Mathematical Interpretation of Formal Systems, Studies in Logic and the Foundations of Mathematics, vol. 16 (1955)), 98-113, (French) · Zbl 0068.24401
[24] Diarra Mbacke, Sokhna, Completeness for domain semirings and star-continuous Kleene algebras with domain (2018), Université Laval: Université Laval Québec, Canada, Master’s thesis
[25] Munn, Walter D., Free inverse semigroups, Proc. Lond. Math. Soc., 3, 3, 385-404 (1974) · Zbl 0305.20033
[26] Pratt, Vaughan R., Semantical considerations on Floyd-Hoare logic, (17th Annual Symposium on Foundations of Computer Science (1976), IEEE), 109-121
[27] Pratt, Vaughan R., A near-optimal method for reasoning about action, J. Comput. Syst. Sci., 20, 2, 231-254 (1980) · Zbl 0424.03010
[28] Preston, Gordon B., Inverse semi-groups, J. Lond. Math. Soc., s1-29, 4, 396-403 (1954) · Zbl 0056.01903
[29] Redko, Volodymyr N., On the determinative aggregate of relationships of the algebra of regular events, Ukr. Mat. Zh., 16, 1, 120-126 (1964), (Russian)
[30] Schein, Boris M., On the theory of generalized groups, Dokl. Akad. Nauk SSSR, 153, 296-299 (1963)
[31] Schein, Boris M., Restrictively multiplicative algebras of transformations, Izv. Vysš. Učebn. Zaved., Mat., 95, 4, 91-102 (1970), (Russian)
[32] Sipser, Michael, Regular languages, (Introduction to the Theory of Computation, Cengage Learning (2012), Boston: Boston Massachusetts, USA), 31-100
[33] Tarski, Alfred, On the calculus of relations, J. Symb. Log., 6, 3, 73-89 (1941) · Zbl 0026.24401
[34] Trokhimenko, Valentin S., Menger’s function systems, Izv. Vysš. Učebn. Zaved., Mat., 11, 71-78 (1973), (Russian)
[35] Wagner, Viktor V., Generalised groups, Proc. Acad. Sci. USSR, 84, 1119-1122 (1952), (Russian)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.