We refine and extend the known results that the set of ordinary binary relations forms a Kleene algebra, the set of up-closed multirelations forms a lazy Kleene algebra, the set of up-closed finite multirelations forms a monodic tree Kleene algebra, and the set of total up-closed finite multirelations forms a probabilistic Kleene algebra. For the refinement, we introduce a notion of type of multirelations. For each of eight classes of relaxation of Kleene algebra, we give a sufficient condition on type
so that the set of up-closed multirelations of
belongs to the class. Some of the conditions are not only sufficient, but also necessary.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten