On Kleene algebras of ternary co-relations

Dolinka Igor: On Kleene algebras of ternary co-relations. In: Acta cybernetica, (14) 4. pp. 583-595. (2000)

[thumbnail of cybernetica_014_numb_004_583-595.pdf]
Cikk, tanulmány, mű

Download (758kB) | Preview


In this paper we investigate identities satisfied by a class of algebras made of ternary co-relations - contravariant ("arrow-reversed") analogues of binary relations. These algebras are equipped with the operations of union, co-relational composition, iteration, converse and the empty co-relation and the so-called diagonal co-relation as constants. Our first result is that the converse-free part of the corresponding equational theory consists precisely of Kleenean equations for relations, or, equivalently, for (regular) languages. However, the rest of the equations, involving the symbol of the converse, are relatively axiomatized by involution axioms only, so that the co-relational converse behaves more like the reversal of languages, rather than the relational converse. Actually, the language reversal is explicitely used to prove this result. Therefore, we conclude that co-relations can offer a better framework than relations for the mathematical modeling of formal languages, as well as many other notions from computer science.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 2000
Volume: 14
Number: 4
ISSN: 0324-721X
Page Range: pp. 583-595
Language: English
Place of Publication: Szeged
Related URLs: http://acta.bibl.u-szeged.hu/38510/
Uncontrolled Keywords: Számítástechnika, Algebra
Additional Information: Bibliogr.: p. 594-595. ; összefoglalás angol nyelven
Subjects: 01. Natural sciences
01. Natural sciences > 01.01. Mathematics
01. Natural sciences > 01.02. Computer and information sciences
Date Deposited: 2016. Oct. 15. 12:25
Last Modified: 2022. Jun. 14. 10:46
URI: http://acta.bibl.u-szeged.hu/id/eprint/12651

Actions (login required)

View Item View Item