DROPS

Document

DOI: 10.4230/LIPIcs.FSCD.2026.15

Undecidability for Semirings with Fixed Points

Authors: Anupam Das, Abhishek De, and Stepan L. Kuznetsov

Published in: LIPIcs, Volume 378, 11th International Conference on Formal Structures for Computation and Deduction (FSCD 2026)

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 inseparability. Our result applies to many theories proposed in the literature, including Conway μ-semirings, Park μ-semirings, and Chomsky algebras.

Cite as

Anupam Das, Abhishek De, and Stepan L. Kuznetsov. Undecidability for Semirings with Fixed Points. In 11th International Conference on Formal Structures for Computation and Deduction (FSCD 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 378, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.FSCD.2026.15,
  author =	{Das, Anupam and De, Abhishek and Kuznetsov, Stepan L.},
  title =	{{Undecidability for Semirings with Fixed Points}},
  booktitle =	{11th International Conference on Formal Structures for Computation and Deduction (FSCD 2026)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-433-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{378},
  editor =	{Pfenning, Frank},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2026.15},
  URN =		{urn:nbn:de:0030-drops-263650},
  doi =		{10.4230/LIPIcs.FSCD.2026.15},
  annote =	{Keywords: Semirings, fixed points, decidability, context-free, inseparability}
}

Search Results

Documents authored by Kuznetsov, Stepan L.

Undecidability for Semirings with Fixed Points

Abstract

Cite as

Thanks for your feedback!

Could not send message