Kleene algebra with commutativity conditions is undecidable

Autor:	de Amorim, Arthur Azevedo, Zhang, Cheng, Gaboardi, Marco
Rok vydání:	2024
Předmět:	Mathematics - Logic Computer Science - Computational Complexity Computer Science - Computation and Language Computer Science - Programming Languages
Druh dokumentu:	Working Paper
Popis:	We prove that the equational theory of Kleene algebra with commutativity conditions on primitives (or atomic terms) is undecidable, thereby settling a longstanding open question in the theory of Kleene algebra. While this question has also been recently solved independently by Kuznetsov, our results hold even for weaker theories that do not support the induction axioms of Kleene algebra. Comment: Published at CSL 2025
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2411.15979 Zobrazit plný text záznamu View this record from Arxiv