The variety of Kleene algebras with conversion is not finitely based

DOI10.1016/S0304-3975(99)00079-1MaRDI QIDQ1978513zbMATH OpenOpenAlexFDO

Authors Siniša Crvenković, Igor Dolinka, Zoltán Ésik

Publication date 4 June 2000

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(99)00079-1

zbMATH Keywords

binary relationsequational theoryrelation algebrasvariety of Kleene algebras

Mathematics Subject Classification ID

Equational classes, universal algebra in model theory (03C05) Relational systems, laws of composition (08A02) Applications of universal algebra in computer science (08A70) Equational logic, Mal'tsev conditions (08B05) Formal languages and automata (68Q45)

Review text

The elements of the full Kleene algebra (with conversion) of a set \(A\) are the binary relations on \(A\), and the operations are those of forming unions, compositions, reflexive, transitive closures and converses of relations. Moreover, the empty relation and the identity relation on \(A\) are included as constants. The variety \(KA^\vee\) generated by all such relation algebras is the variety of Kleene algebras. The variety \(KA\) of conversion-free Kleene algebras is obtained similarly by omitting the conversion operation from the relation algebras. It is known that the equational theory of the variety \(KA\) is not finitely based. In this paper the authors prove in two different ways that the same holds for the variety \(KA^\vee\).

Recommendations

• Equational properties of Kleene algebras of relations with conversion
• On Kleene algebras
• Notes on equational theories of relations
• On Kleene algebras of ternary co-relations
• Kleene algebra with converse

Cites work

• Complete systems of \(\mathcal B\)-rational identities
• Equational axioms for regular sets
• Equational properties of Kleene algebras of relations with conversion
• Group axioms for iteration
• scientific article; zbMATH DE number 67032 (Why is no real title available?)
• scientific article; zbMATH DE number 3561239 (Why is no real title available?)
• scientific article; zbMATH DE number 549971 (Why is no real title available?)
• scientific article; zbMATH DE number 1972804 (Why is no real title available?)
• scientific article; zbMATH DE number 3290336 (Why is no real title available?)
• scientific article; zbMATH DE number 3316966 (Why is no real title available?)
• scientific article; zbMATH DE number 3366846 (Why is no real title available?)
• Nonfinite axiomatizability of the equational theory of shuffle
• Notes on equational theories of relations
• On Kleene algebras
• The equational logic of fixed points
• Two Complete Axiom Systems for the Algebra of Regular Events

Cited in

(14)

• On equations for union-free regular languages
• The max-plus algebra of the natural numbers has no finite equational basis
• Finite basis problem for involution monoids of unitriangular Boolean matrices
• A non-finitely based involution semigroup of order five
• The monoid of \(2 \times 2\) triangular Boolean matrices under skew transposition is non-finitely based
• IDEMPOTENT DISTRIBUTIVE SEMIRINGS WITH INVOLUTION
• Finite basis problem for Catalan monoids with involution
• THE FINITE BASIS PROBLEM FOR INVOLUTION SEMIGROUPS OF TRIANGULAR MATRICES
• Finite basis problem for Lee monoids with involution
• On Kleene algebras
• Representations and identities of Baxter monoids with involution
• Axiomatizability of positive algebras of binary relations
• Equational theories of the Boolean matrix monoid \(\mathscr{BR}_n\) with involutions
• Abstract abstract reduction

This page was built for publication: The variety of Kleene algebras with conversion is not finitely based

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1978513)