Abstract: 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.
Recommendations
Cites work
- A completeness theorem for Kleene algebras and the algebra of regular events
- A near-optimal method for reasoning about action
- An equational axiomatization of dynamic negation and relational composition
- Axiomatizability of representable domain algebras
- Domain Axioms for a Family of Near-Semirings
- Duality and Equational Theory of Regular Languages
- Free Inverse Semigroups
- Free right type A semigroups
- scientific article; zbMATH DE number 3115891 (Why is no real title available?)
- scientific article; zbMATH DE number 3751028 (Why is no real title available?)
- scientific article; zbMATH DE number 3497806 (Why is no real title available?)
- scientific article; zbMATH DE number 1086671 (Why is no real title available?)
- scientific article; zbMATH DE number 941396 (Why is no real title available?)
- scientific article; zbMATH DE number 3430952 (Why is no real title available?)
- scientific article; zbMATH DE number 3224572 (Why is no real title available?)
- scientific article; zbMATH DE number 3316966 (Why is no real title available?)
- scientific article; zbMATH DE number 3317807 (Why is no real title available?)
- scientific article; zbMATH DE number 3074084 (Why is no real title available?)
- Internal axioms for domain semirings
- Inverse Semi-Groups
- Kleene algebra with domain
- Notes on equational theories of relations
- On the calculus of relations
- Propositional dynamic logic of regular programs
- Relation algebras by games
- Stone duality, topological algebra, and recognition.
- THE FREE AMPLE MONOID
- The Structure of the One-Generated Free Domain Semiring
Cited in
(9)- The Structure of the One-Generated Free Domain Semiring
- MV-algebras freely generated by finite Kleene algebras.
- scientific article; zbMATH DE number 1047921 (Why is no real title available?)
- Kleene algebra with domain
- Embedding Kozen-Tiuryn logic into residuated one-sorted Kleene algebra with tests
- On the complexity of Kleene algebra with domain
- The equational theory of Kleene lattices
- Domain reasoning in TopKAT
- On the expressive power of Kleene algebra with domain
This page was built for publication: Free Kleene algebras with domain
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2210872)
