Kleene algebra with commutativity conditions is undecidable

November 24, 2024 · The Ethereal · 🏛 Annual Conference for Computer Science Logic

🔮 THE ETHEREAL: The Ethereal
Pure theory — exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Arthur Azevedo de Amorim, Cheng Zhang, Marco Gaboardi arXiv ID 2411.15979 Category math.LO: Logic Cross-listed cs.CC, cs.CL, cs.LO, cs.PL Citations 3 Venue Annual Conference for Computer Science Logic Last Checked 1 month ago
Abstract
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.
Community shame:
Not yet rated
📄 View on arXiv 🌐 View on ar5iv 📑 PDF 🎉 Report Code Found
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

📜 Similar Papers

In the same crypt — Logic