Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

Free Kleene algebras with domain

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.
Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal.univ-cotedazur.fr/hal-03018506
Contributeur : Brett Mclean <>
Soumis le : dimanche 22 novembre 2020 - 19:02:50
Dernière modification le : mercredi 6 janvier 2021 - 22:20:02

Fichier

 Accès restreint
Fichier visible le : 2022-09-29

Connectez-vous pour demander l'accès au fichier

Identifiants

  • HAL Id : hal-03018506, version 1

Collections

Citation

Brett Mclean. Free Kleene algebras with domain. Journal of Logical and Algebraic Methods in Programming, Elsevier, 2019. ⟨hal-03018506⟩

Partager

Métriques

Consultations de la notice

15

Données de recherche

doi: web.