Undecidability of theories of semirings with fixed points
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911332455940096 |
|---|---|
| author | Das, Anupam De, Abhishek Kuznetsov, Stepan L. |
| author_facet | Das, Anupam De, Abhishek Kuznetsov, Stepan L. |
| contents | In this work we prove the undecidability (and $Σ^0_1$-completeness) of several theories of semirings with fixed points. The generality of our results stems from recursion theoretic methods, namely the technique of effective inseperability. Our result applies to many theories proposed in the literature, including Conway $μ$-semirings, Park $μ$-semirings, and Chomsky algebras. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_19401 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Undecidability of theories of semirings with fixed points Das, Anupam De, Abhishek Kuznetsov, Stepan L. Logic Logic in Computer Science In this work we prove the undecidability (and $Σ^0_1$-completeness) of several theories of semirings with fixed points. The generality of our results stems from recursion theoretic methods, namely the technique of effective inseperability. Our result applies to many theories proposed in the literature, including Conway $μ$-semirings, Park $μ$-semirings, and Chomsky algebras. |
| title | Undecidability of theories of semirings with fixed points |
| topic | Logic Logic in Computer Science |
| url | https://arxiv.org/abs/2512.19401 |