Equational theories of relations and regular sets. (English) Zbl 0874.08002

Ito, Masami (ed.) et al., Words, languages and combinatorics II. Proceedings of the 2nd international conference, Kyoto, Japan, August 25-28, 1992. Singapore: World Scientific. 40-48 (1994).
Summary: We describe explicitly the free algebras in the variety \(\text{REL}^\vee\) generated by all algebras of binary relations with the operations of union, composition, conversion and reflexive-transitive closure and neutral elements 0 (the empty relation) and 1 (the identity relation). Using the description of the free algebras, we obtain a set of equational axioms for \(\text{REL}^\vee\). We show the corresponding equational theory is decidable by reducing the problem to a question about regular sets.
For the entire collection see [Zbl 0868.00046].


08A70 Applications of universal algebra in computer science
68Q70 Algebraic theory of languages and automata
08B20 Free algebras
03D05 Automata and formal grammars in connection with logical questions
03B25 Decidability of theories and sets of sentences