The equational theory of Kleene algebra with commutativity conditions on primitives is undecidable, and this holds already for pre-Kleene algebras without induction axioms, with Sigma-0-1 completeness.
On the decidability of some problems about rational subsets of free partially commutative monoids
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
fields
math.LO 1years
2024 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Kleene algebra with commutativity conditions is undecidable
The equational theory of Kleene algebra with commutativity conditions on primitives is undecidable, and this holds already for pre-Kleene algebras without induction axioms, with Sigma-0-1 completeness.