Kleene algebra with commutativity conditions is undecidable
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912163641163776 |
|---|---|
| author | de Amorim, Arthur Azevedo Zhang, Cheng Gaboardi, Marco |
| author_facet | de Amorim, Arthur Azevedo Zhang, Cheng Gaboardi, Marco |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_15979 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Kleene algebra with commutativity conditions is undecidable de Amorim, Arthur Azevedo Zhang, Cheng Gaboardi, Marco Logic Computational Complexity Computation and Language Logic in Computer Science Programming Languages 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. |
| title | Kleene algebra with commutativity conditions is undecidable |
| topic | Logic Computational Complexity Computation and Language Logic in Computer Science Programming Languages |
| url | https://arxiv.org/abs/2411.15979 |