Decidability of the inclusion problem for finite codes: embedding a finite code into a finite maximal code

A basic open decision problem in the algebraic theory of variable-length codes asks whether one can decide, given a finite code $X$ over a finite alphabet $A$, whether $X$ is contained in some finite maximal code over $A$ (the inclusion problem; its decidability is the inclusion conjecture). Negative instances exist since Restivo (1977) constructed finite codes with no finite completion, and De Felice (2007) proved decidability for codes of the special form $X \cup a^n$ with $X \subseteq a^*(A\setminus\{a\})a^*$ and $\Omega(n)\le 2$, where $\Omega(n)$ counts the prime factors of $n$ with multiplicity; in that case the containing code may even be taken factorizing. As of De Felice's 2023 follow-up — and of Cordero's 2024 extension of the triangle conjecture to $n$ with at most three prime factors — both restrictions remain: decidability for $\Omega(n)\ge 3$, and for arbitrary finite codes, is open. The problem asks for a proven decision algorithm for the general case, or a proof of undecidability.

Background

A code over a finite alphabet $A$ is a set $X \subseteq A^*$ of words such that every word of the submonoid $X^*$ (all concatenations of words of $X$) has a unique factorization over $X$; equivalently, $X$ is a basis of a free submonoid of the free monoid $A^*$. A code is maximal if it is inclusion-maximal among codes over $A$; every finite maximal code contains a power $a^n$ of each letter $a \in A$ (the order of $a$). Maximal codes always exist by Zorn's lemma, but they may be infinite, and Restivo (1977) exhibited finite codes not contained in any finite maximal code. The inclusion problem asks, for a given finite code $X$, whether a finite maximal code $C \supseteq X$ exists (a finite completion of $X$); the inclusion conjecture asserts that this problem is decidable.

The structural side of the question comes from Schützenberger's algebraic approach. Identify a finite language with its characteristic polynomial in $\mathbb{Z}\langle A\rangle$ (the ring of polynomials in noncommuting letters $A$ with integer coefficients; $\underline{X}$ denotes the formal sum of the words of $X$, and $1$ is the empty word). Reutenauer (1985) proved that every finite maximal code $C$ satisfies $\underline{C}-1=P(A-1)S$ for some polynomials $P,S \in \mathbb{Z}\langle A\rangle$; the factorization conjecture, formulated by Schützenberger and open since the 1980s, asserts that $P,S$ can always be chosen with coefficients $0$ and $1$, i.e. $\underline{C}-1=\underline{P}(A-1)\underline{S}$ for finite subsets $P,S \subseteq A^*$. Codes with such a positive factorization are called factorizing codes. Two further long-standing conjectures on finite maximal codes, the commutative equivalence conjecture (every finite maximal code is commutatively equivalent to a prefix code, i.e. uses each letter the same total number of times as some code in which no word is a prefix of another) and the triangle conjecture (every finite bayonet code, i.e. a code whose words all have the form $a^i b a^j$, that embeds in a finite maximal code satisfies $\mathrm{Card}(X) \le \max\{|x| : x \in X\}$; the unrestricted form was refuted by Shor in 1985), are related: factorizing codes are commutatively prefix, and both are connected to factorizations of cyclic groups.

A pair $(R,T)$ of subsets is a factorization of the cyclic group $\mathbb{Z}_n$ if every residue class modulo $n$ is uniquely $r+t$ with $r \in R$, $t \in T$. Krasner factorizations (those obtained from a chain of divisors of $n$ via products of geometric-like polynomial quotients) and Hajós factorizations (a class built from Krasner factorizations by a substitution operation) control the structure of factorizing codes intersected with $a^*ba^*$: De Felice introduced good arrangements of such intersections, proved that good-arrangement sets coming from a finite maximal code are constrained by Krasner companions, and showed that some good-arrangement sets are not codes, so the correspondence is delicate. Let $\Omega(n)$ denote the number of factors in the prime factorization of $n$ (with multiplicity). De Felice (2007) proved that for $X \subseteq a^*(A\setminus\{a\})a^*$ it is decidable whether there exist $n$ with $\Omega(n) \le 2$ and a finite maximal factorizing code $C$ with $X \cup a^n \subseteq C$ (in the variant where $n$ is given as part of the input code, decidability for codes $Y \cup a^n \subseteq a^*Ba^* \cup a^*$ was established in her 2023 paper); her companion paper (2007, IJAC) treats the corresponding completions constructively. Zhang and Shum (2017) proved a structural theorem tying arbitrary finite maximal codes to factorizations of cyclic groups, and De Felice (2023) re-proved it, deduced the triangle conjecture for $X \cap a^*Ba^*$ when $a^{pq} \in X$ ($p,q$ prime), and recovered the decidability result for $n$ a product of at most two primes — still inside the $\Omega(n) \le 2$ barrier. Cordero (2024) then settled the triangle conjecture for codes $X \cup a^n$ with $X \subseteq a^* b a^*$ and $\mathrm{Card}(X) = n$ when $n$ has at most three prime factors or the form $pq^k$ ($p,q$ prime) — the first headway past that barrier — but did not decide the inclusion problem. What no later work touches is the decision problem for general $n$ and for arbitrary finite codes, and the factorization conjecture itself remains open.

Problem Statement

Decide, given an arbitrary finite code $X$ over a finite alphabet $A$, whether there exists a finite maximal code $C$ over $A$ with $X \subseteq C$ (the inclusion problem for finite codes). The inclusion conjecture asserts that this problem is decidable. The question is open in exactly two directions left by the known partial results: (a) when $X = Y \cup a^n$ with $Y \subseteq a^*(A\setminus\{a\})a^*$ but $\Omega(n) \ge 3$ (three or more prime factors, counted with multiplicity), where decidability — and even a constructive characterization of which such $Y$ admit a finite factorizing supercode — is unknown; and (b) for arbitrary finite codes not concentrated in $a^*Ba^* \cup a^*$ around a single power of one letter (here $B$ ranges over the letters of $A$ distinct from $a$). The question is resolved by a total, sound and complete decision algorithm for the general problem, or by a proof that the problem is undecidable.

References

1. Clelia De Felice, On factorizing codes: Structural properties and related decision problems, Advances in Applied Mathematics 39(2) (2007) 173–196. DOI: 10.1016/j.aam.2005.12.002. https://doi.org/10.1016/j.aam.2005.12.002
2. Antonio Restivo, On codes having no finite completions, Discrete Mathematics 17(3) (1977) 309–316. DOI: 10.1016/0012-365X(77)90164-9. https://doi.org/10.1016/0012-365X(77)90164-9
3. Christophe Reutenauer, Noncommutative factorization of variable-length codes, Journal of Pure and Applied Algebra 36 (1985) 167–186. DOI: 10.1016/0022-4049(85)90069-6. https://doi.org/10.1016/0022-4049(85)90069-6
4. Clelia De Felice, Finite completions via factorizing codes, International Journal of Algebra and Computation 17(4) (2007) 715–760. DOI: 10.1142/S0218196707003871. https://doi.org/10.1142/S0218196707003871
5. P.W. Shor, A counterexample to the triangle conjecture, Journal of Combinatorial Theory, Series A 38 (1985) 110–112. DOI: 10.1016/0097-3165(85)90032-9. https://doi.org/10.1016/0097-3165(85)90032-9
6. Clelia De Felice, A note on the factorization conjecture, Acta Informatica 50(7–8) (2013) 381–402. DOI: 10.1007/s00236-013-0187-1. Preprint: arXiv:1205.2310. https://doi.org/10.1007/s00236-013-0187-1
7. Clelia De Felice, Some conjectures on codes, preprint (2016). arXiv:1611.04580. https://arxiv.org/abs/1611.04580
8. Liang Zhang, K.P. Shum, Finite maximal codes and triangle conjecture, Discrete Mathematics 340(3) (2017) 541–549. DOI: 10.1016/j.disc.2016.10.008. https://doi.org/10.1016/j.disc.2016.10.008
9. Clelia De Felice, Finite maximal codes and factorizations of cyclic groups, Journal of Automata, Languages and Combinatorics 28(4) (2023) 287–338. DOI: 10.25596/jalc-2023-287. Preprint: arXiv:2202.09675. https://doi.org/10.25596/jalc-2023-287
10. Christophe Cordero, Factorizations of Cyclic Groups and Bayonet Codes, Journal of Automata, Languages and Combinatorics 29(1) (2024) 011–039. DOI: 10.25596/jalc-2024-011. Preprint: arXiv:2301.13566. https://doi.org/10.25596/jalc-2024-011