Notes on equational theories of relations
type: Item
instance of: scholarly article
title: Notes on equational theories of relations
zbMATH Open document ID: 0834.08004
DOI: 10.1007/BF01190768
author: Gh. Ştefănescu
author: Stephen L. Bloom
author: Zoltán Ésik
published in: Algebra Universalis
publication date: 1995-02-22T00:00:00Z
review text: The paper is a contribution to the equational theory of semirings, Kleene algebras and relation algebras. It studies several equational varieties. The equational class \(\text{REL}^\vee\) is generated by all algebras of binary relations on a set \(A\), with operations union, composition, converse and star (reflexive transitive closure), and constants empty and identity relation. A subclass is given by the theory of full, i.e. total and surjective, relations. The variety \(L^\vee\) is generated by all algebras of formal languages in a free monoid, with operations union, concatenation, reverse and Kleene star, and constants empty language and language consisting of the empty word only. The main results are explicit descriptions of the free algebras in these classes and proofs that the corresponding equational theories are decidable. These results are interesting for formal languages, relations and dynamic algebras.
Mathematics Subject Classification ID: 08A70
Mathematics Subject Classification ID: 08B20
Mathematics Subject Classification ID: 03B25
Mathematics Subject Classification ID: 16Y60
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 724105
zbMATH Keywords: equational theory
zbMATH Keywords: semirings
zbMATH Keywords: Kleene algebras
zbMATH Keywords: relation algebra
zbMATH Keywords: binary relations
zbMATH Keywords: algebras of formal languages in a free monoid
zbMATH Keywords: Kleene star
zbMATH Keywords: free algebras
zbMATH Keywords: dynamic algebras
MaRDI profile type: Publication
cites work: Matrix and matricial iteration theories. I
cites work: Equational axioms for regular sets
cites work: Q5639639
cites work: Q4079524
cites work: Equational properties of Kleene algebras of relations with conversion
cites work: Q3994922
cites work: Complete systems of \(\mathcal B\)-rational identities
cites work: Q4273477
cites work: On the calculus of relations
full work available at URL: https://doi.org/10.1007/bf01190768
OpenAlex ID: W2049894505
description: scientific article; zbMATH DE number 724105