Undecidability of theories of semirings with fixed points

Anupam Das; Abhishek De; Stepan L. Kuznetsov

doi:10.48550/arXiv.2512.19401

Undecidability of theories of semirings with fixed points

Anupam Das
, Abhishek De
, Stepan L. Kuznetsov

Computer Science

Research output: Working paper/Preprint › Preprint

Abstract

In this work we prove the undecidability (and Σ⁰₁-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.

Original language	English
Publisher	arXiv
DOIs	https://doi.org/10.48550/arXiv.2512.19401
Publication status	Published - 22 Dec 2025

Access to Document

10.48550/arXiv.2512.19401Licence: Creative Commons: Attribution (CC BY)

2512.19401v1Other version, 542 KBLicence: Creative Commons: Attribution (CC BY)

Cite this

@techreport{db54fee709ff4c088a009893f55c1e55,

title = "Undecidability of theories of semirings with fixed points",

abstract = "In this work we prove the undecidability (and Σ01-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.",

author = "Anupam Das and Abhishek De and Kuznetsov, \{Stepan L.\}",

year = "2025",

month = dec,

day = "22",

doi = "10.48550/arXiv.2512.19401",

language = "English",

publisher = "arXiv",

type = "WorkingPaper",

institution = "arXiv",

}

TY - UNPB

T1 - Undecidability of theories of semirings with fixed points

AU - Das, Anupam

AU - De, Abhishek

AU - Kuznetsov, Stepan L.

PY - 2025/12/22

Y1 - 2025/12/22

N2 - In this work we prove the undecidability (and Σ01-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.

AB - In this work we prove the undecidability (and Σ01-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.

U2 - 10.48550/arXiv.2512.19401

DO - 10.48550/arXiv.2512.19401

M3 - Preprint

BT - Undecidability of theories of semirings with fixed points

PB - arXiv

ER -

Undecidability of theories of semirings with fixed points

Abstract

Access to Document

Fingerprint

Cite this