Undecidability of theories of semirings with fixed points
Anupam Das 1, Abhishek De 2, Stepan L. Kuznetsov 3 · 2025
Read Undecidability of theories of semirings with fixed points by Anupam Das 1, Abhishek De 2, Stepan L. Kuznetsov 3 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-19401.txt.
Introduction
Anupam Das, Abhishek De, and Stepan Kuznetsov prove that several theories of semirings with fixed points admit no decision procedure at all. A semiring is a set with two operations that act much like plus and times, but with no need for minus. A fixed point adds a way to name the least solution of an equation, much like a loop in a program.
The authors use a method from recursion theory to show that no algorithm can settle all true claims in these systems. The verdict covers Conway and Park mu-semirings and Chomsky algebras, and more systems of the same kind.
Catalog record
| CREATOR | Anupam Das 1, Abhishek De 2, Stepan L. Kuznetsov 3 |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 51 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-19401
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Undecidability of theories of semirings with fixed points Anupam Das 1, Abhishek De 2, Stepan L. Kuznetsov 3 Abstract . In this work we prove the undecidability (and Σ 1 0 \Sigma^{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 μ \mu -semirings, Park μ \mu -semirings, and Chomsky algebras. 1. Introduction The context-free languages (CFLs) may be presented as the least solutions to certain systems of algebraic inequalities, by construing context-free grammars (CFGs) as such. It is well known that the resolution of such simultaneous fixed points may be reduced to unary ones, by way of Bekić’s Lemma , [ 1 ] . Indeed already in the early ’70s Gruska observed that expressions for CFLs could be obtained by an extension of usual regular expressions by an ‘iteration’ operator for computing (least) fixed points. Nowadays these are known as \mu -expressions [ 21 , 6 , 7 ] . 1 1 1 Here the notation ‘ \mu ’ insists that the fixed points named in the syntax are least , instead of, say, greatest or even arbitrary fixed points. Algebraic theories of regular expressions are based on (idempotent) semirings with an appropriate * operation, for instance Kleene algebras (cf., e.g., [ 14 ] ). Duly, analogous structures for \mu -expressions are based on (idempotent) semirings with fixed points . Similarly to regular expressions, in the last few decades a number of formulations of semirings with fixed points have appeared throughout the literature in formal language theory, logic, and algebra [ 2 , 21 , 6 , 7 , 12 , 13 , 5 , 8 , 20 ] . However until now, as far as we know, the (un)decidability of most of these equational theories has remained open. This is in stark contrast to the situation for Kleene algebras, over regular expressions, where the complexity of equational and Horn theories, with and without continuity, is now well understood (see, e.g., [ 16 , 4 ] ). In this work we address this situation by showing undecidability (in fact \Sigma^{0}_{1} -completeness) for a range of theories of (not necessarily continuous) semirings with fixed points, including many of the ones occurring in the literature, in particular from [ 21 , 6 , 7 , 8 ] . 1.1. Previous work Leiß investigated several classes of idempotent semirings with fixed points, all of which satisfy the induction axioms characterising \mu xe(x) as the least prefixed point of the operation x\mapsto e(x) . This interpretation of least fixed points is recovered from the famous Knaster-Tarski fixed point theorem, and is the standard way to present axiomatic theories with forms of (co)induction. Ésik and Leiß showed that reduction of CFGs to Greibach normal form [ 9 ] can be validated in a purely equational theory of semirings with fixed points (not necessarily satisfying induction), Conway \mu -semirings [ 6 , 7 ] . Grathwohl, Henglein and Kozen gave a sound and complete (infinitary) axiomatisation of CFL inclusions by way of \mu -expressions [ 8 ] (note that this problem is \Pi^{0}_{1} -complete). In particular they introduced the notion of a Chomsky algebra , an algebraically closed idempotent semiring. These turn out to be nothing more than idempotent Park \mu -semirings of [ 21 , 6 , 7 ] , where \mu -expressions give a naming convention for solutions to polynomial systems. [ 8 ] showed that the theory of \mu -continuous Chomsky algebras is sound and complete for CFL inclusions. Later further metalogical results were established for Chomsky algebras and friends. For instance Leiß showed that the matrix ring of a \mu -continuous Chomsky algebra is again \mu -continuous. Two of the authors of the present work recovered the completeness result of [ 8 ] via proof theoretic means, even establishing a stronger ‘cut-free’ completeness result [ 3 ] . In the same work they also proposed non-wellfounded systems for both CFLs, via \mu -expressions, and an extension to \omega -words, using greatest fixed points . 1.2. Contributions In this work we show undecidability, in fact \Sigma^{0}_{1} -completeness, for a range of theories of semirings with fixed points. We give a basic equational axiomatisation \mu\mathsf{S}_{\not{\hskip 0.81949pt1}} of semirings (not necessarily with identity) with a \mu operator denoting (not necessarily least) fixed points. In particular this theory is more general (i.e. weaker) than the Conway \mu -semirings, Park \mu -semirings and Chomsky algebras from earlier works. Our main result is that any recursively enumerable extension of \mu\mathsf{S}_{\not{\hskip 0.81949pt1}} sound for the usual language model is undecidable, and in fact \Sigma^{0}_{1} -complete. In particular Conway \mu -semirings, Park \mu -semirings and Chomsky algebras have undecidable equational theories. To achieve such generality we employ methods from recursion theory, exploiting the technique of effective inseparability . These methods were successfully employed in earlier works by one of the authors, in particular showing the undecidability of the equational theory of action lattices [ 18 , 19 ] , a longstanding open problem, and the same for commutative action lattices [ 17 ] . 1.3. Structure of the paper In Section 2 we introduce a basic theory \mu\mathsf{S} of semirings (with identity) with fixed points, as well as other theories from the literature. In Section 3 we prove the effective inseparability of two problems on CFGs, ‘non-totality’ \bar{\mathbf{T}} and ‘regular totality’ \mathbf{R} , by reduction to a more well known effectively inseparable pair, ‘halting’ and ‘looping’ Turing machines. In Section 4 we show the undecidability of any r.e. extension of \mu\mathsf{S}+{} idempotency , e+e=e , sound for the language model. In Section 5 we improve this result to theories without identity and idempotency, by a sort of interpretation of idempotency via fixed points. Finally we make some concluding remarks in Section 6 . 2. Some theories of semirings with fixed points Let \mathcal{A} be a finite alphabet and \mathcal{V} be a countably infinite set of variables disjoint from \mathcal{A} . We consider \mu -expressions e,f, etc. generated by the following grammar: e,f,\dots\quad::=\quad 0\quad\mid\quad 1\quad\mid\quad a\in\mathcal{A}\quad\mid\quad x\in\mathcal{V}\quad\mid\quad e+f\quad\mid\quad e\cdot f\quad\mid\quad\mu xe We usually just write ef instead of e\cdot f . Structures interpreting \mu -expressions, formally, must be defined appropriately taking account of variable binding and compatible with substitution. A formal exposition can be found in e.g. [ 7 , 20 ] , so here we give only examples: Example 1 (Languages) . Temporarily expand the syntax of expressions to include each language A\subseteq\mathcal{A}^{*} as a new constant symbol. We associate to each closed \mu -expression e (of this expanded syntax) a language \mathcal{L}(e)\subseteq\mathcal{A}^{*} as follows: \begin{array}[]{r@{\ \df\ }l}\mathcal{L}(0)\ :=&0\\ \mathcal{L}(1)\ :=&\{\varepsilon\}\\ \mathcal{L}(a)\ :=&\{a\}\\ \mathcal{L}(A)\ :=&A\\ \mathcal{L}(e+f)\ :=&\mathcal{L}(e)\cup\mathcal{L}(f)\\ \mathcal{L}(ef)\ :=&\{uv:u\in\mathcal{L}(e)\ \&\ v\in\mathcal{L}(f)\}\\ \vskip 6.0pt plus 2.0pt minus 2.0pt\cr\mathcal{L}(\mu xe(x))\ :=&\bigcap\{A:\mathcal{L}(e(A))\subseteq A\}\end{array} Every symbol is interpreted by \mathcal{L}(\cdot) as a monotone operation, with respect to (\mathcal{P}(\mathcal{A}^{*}),\subseteq) . The Knaster-Tarski fixed point theorem tells us that monotone operations on complete lattices have least fixed points, 2 2 2 Indeed, they further have a complete sublattice of fixed points, in particular including a greatest fixed point. in particular with the least fixed point of