Decidability of the inclusion problem for finite codes: deciding whether a finite code can be embedded in a finite maximal code

A code is a set of words over a finite alphabet in which every word admits at most one factorization (the basis of a free submonoid of the free monoid), and a maximal code is a code not properly contained in a larger code over the same alphabet. Every code can be completed to a maximal code, but Restivo (1977) exhibited finite codes that are contained in no finite maximal code, so the following decision problem is nontrivial: given an arbitrary finite code, decide whether it is embedded in some finite maximal code. This is the inclusion problem; the assertion that it is decidable is the inclusion conjecture. Partial results are known — prefix-suffix codes and codes of the form $a^Pba^Q\cup\{a^n\}$ with $(P,Q)$ a Hajós factorization are always completable, and embeddability is decidable for codes $Y\cup a^n\subseteq a^*Ba^*\cup a^*$ when $n$ has at most two prime factors — but the general problem remains open as of the most recent literature (2023–2024). The problem is tightly connected to the factorization, commutative-equivalence, and triangle conjectures on finite maximal codes: for instance, deciding whether Shor's 1985 bayonet counterexample code has a finite maximal completion is open, and a positive answer would refute two of those conjectures at once.

Background

Fix a finite alphabet $A$ and write $A^*$ for the free monoid of all words over $A$ (with concatenation) and $A^+=A^*\setminus\{1\}$ for the nonempty words, where $1$ is the empty word. A subset $X\subseteq A^+$ is a code (a variable-length code, the basis of a free submonoid) if every word in $X^*$ factors uniquely as a product of elements of $X$; equivalently, $X$ is uniquely decipherable. A code $X$ over $A$ is maximal if no code over $A$ properly contains it. By Zorn's lemma every code extends to a maximal code, but the extension is generally infinite. The classical finite completion problem asks when a finite code is contained in some finite maximal code. Restivo (1977) gave the first example of a finite code with no finite completion (a four-word binary code, displayed in later papers as $\{a^5, ab, b, ba^2\}$), which makes the associated decision problem — the inclusion problem: given a finite code $X$, does a finite maximal code containing $X$ exist? — nontrivial, and motivates the inclusion conjecture: the inclusion problem is decidable (terminology of De Felice). Several families are known to be completable: Restivo, Salemi and Sportelli (1989) proved that every finite prefix-suffix code — a code obtained from the alphabet by a finite chain of prefix and suffix compositions, where a prefix code is one in which no word is a proper left factor of another and a suffix code is defined dually — is contained in a finite maximal code; Lam (1997) proved the same for codes of the form $a^Pba^Q\cup\{a^n\}$ over $\{a,b\}$ where the pair $(P,Q)$ of exponent sets is a factorization of the cyclic group $\mathbb{Z}_n$ in the sense that every residue modulo $n$ is uniquely $p+q$ with $p\in P$, $q\in Q$, and this factorization is of Hajós type (built by Hajós's recursive method). The structural theory behind these results connects code completion to factorizations of cyclic groups. A finite maximal code $C$ always contains a power $a^n$ of each letter $a$ (the order of $a$ relative to $C$), and the words of $C\cap a^*ba^*$ can be arranged in matrices whose row and column index sets factor $\mathbb{Z}_n$ (Zhang–Shum 2017, with earlier versions by De Felice and by Perrin and Schützenberger). Two special classes matter: Krasner factorizations (arising from chains of divisors of $n$ via the Krasner–Ranulac circle-division polynomials) and Hajós factorizations (constructed by Hajós's recursive method; $n$ is a Hajós number when every factorization of $\mathbb{Z}_n$ is of Hajós type — exactly the $n$ of the forms $p^kq$, $p^2q^2$, $p^2qr$, $pqrs$ up to subgroups, for primes $p,q,r,s$). Szabó (2006) studied completion criteria through the Rédei property of finite abelian groups (every factorization of the group into subsets containing the identity has a factor contained in a proper subgroup), another group-side invariant relevant to completing codes over two-letter alphabets. The problem is also entangled with three celebrated conjectures about finite maximal codes: the factorization conjecture (every finite maximal code $C$ satisfies $\underline{C}=P(\underline{A}-1)S+1$ for finite sets $P,S$, where $\underline{X}$ is the characteristic polynomial of $X$; codes satisfying it are called factorizing), the commutative-equivalence conjecture (every finite maximal code is commutatively equivalent to a prefix code, i.e., matched word-by-word with a prefix code after permuting letters within each word), and the triangle conjecture restricted to embeddable codes: every finite bayonet code (a code whose words all have the form $a^iba^j$) that is contained in a finite maximal code satisfies $\mathrm{Card}(X)\le\max\{|x|:x\in X\}$. Shor (1985) constructed a finite bayonet code violating this inequality, which forced the conjectures to be restricted from arbitrary codes to finite maximal codes and their subsets; whether Shor's code — or any of the later non-commutatively-prefix bayonet codes found by Cordero (2019) — is contained in a finite maximal code is open, and Cordero (2024) shows any such completion would have to involve a power $a^n$ with $n\ge 36$ a non-cbc-Hajós number (Cordero's completion-specific predicate: $n$ is a cbc Hajós number when it is a product of at most three primes or of the form $p^kq$, whose smallest non-members are $36=p^2q^2$, $60=p^2qr$ and $72$ — unlike the group-factorization-theoretic Hajós number defined above, for which $36$ and $60$ are Hajós). On the decidability side, De Felice (2007) gave the first algorithms: for codes of the shape $Y\cup a^n$ with $Y\subseteq a^*Ba^*$ and $\mathrm{Card}(Y\cap a^*ba^*)=n$ where $\Omega(n)\le 2$ ($\Omega(n)$ the number of prime factors of $n$ counted with multiplicity), embeddability into a finite (indeed factorizing) maximal code is decidable, via a decidable structural criterion on arrangements of the words $a^iba^j$; De Felice (2023) re-proved and extended this, and Cordero (2024) proved that for $n$ a cbc Hajós number (in particular every $n<36$) embeddability of $\{a^n\}\cup X$ with $X\subseteq a^*\omega a^*$ coincides with being a prefix-suffix code — explicitly 'a small step towards the inclusion problem'. The general case — arbitrary finite codes over arbitrary finite alphabets — remains open; the standard reference treatment is Berstel, Perrin and Reutenauer's monograph Codes and Automata.

Problem Statement

Given a finite alphabet $A$ and a finite code $X\subseteq A^+$ (an arbitrary finite uniquely decipherable set of words), the inclusion problem asks whether there exists a finite maximal code $C$ over $A$ — that is, a finite code over $A$ not properly contained in any larger code over $A$ — with $X\subseteq C$; equivalently, whether $X$ has a finite completion. Decide whether this problem is algorithmically decidable: either (i) exhibit a terminating algorithm which, on input of any finite code $X$ over any finite alphabet, correctly decides whether $X$ is contained in some finite maximal code over that alphabet, together with a proof of its correctness (confirming the inclusion conjecture of De Felice), or (ii) prove that no such algorithm exists (refuting the inclusion conjecture). No restriction on alphabet size, number of words, word shape, or cardinality $\mathrm{Card}(X)$ is admissible; the decision procedure, if one exists, must handle arbitrary finite codes, including codes $X\cup a^n$ with $n$ a non-cbc-Hajós number (in particular $n\ge 36$) and non-commutatively-prefix bayonet codes such as Shor's example, for which the answer is currently unknown even instance by instance.

References

1. Clelia De Felice, 'On factorizing codes: structural properties and related decision problems', Advances in Applied Mathematics 39 (2007) 173–196. DOI: 10.1016/j.aam.2005.12.002, https://doi.org/10.1016/j.aam.2005.12.002
2. Clelia De Felice, 'Finite completions via factorizing codes', International Journal of Algebra and Computation 17 (2007) 715–760. DOI: 10.1142/S0218196707003871, https://doi.org/10.1142/S0218196707003871
3. Clelia De Felice, 'Some conjectures on codes', arXiv:1611.04580 (2016). arXiv:1611.04580, https://arxiv.org/abs/1611.04580
4. 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, arXiv:2202.09675, https://doi.org/10.25596/jalc-2023-287
5. Christophe Cordero, 'Factorizations of cyclic groups and bayonet codes', Journal of Automata, Languages and Combinatorics 29(1) (2024) 11–39. DOI: 10.25596/jalc-2024-011, arXiv:2301.13566, https://doi.org/10.25596/jalc-2024-011
6. Christophe Cordero, 'A note with computer exploration on the triangle conjecture', in: Language and Automata Theory and Applications (LATA 2019), Lecture Notes in Computer Science, pages 409–420. DOI: 10.1007/978-3-030-13435-8_30, https://doi.org/10.1007/978-3-030-13435-8_30
7. Peter 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
8. Antonio Restivo, 'On codes having no finite completions', Discrete Mathematics 17 (1977) 309–316. DOI: 10.1016/0012-365X(77)90164-9, https://doi.org/10.1016/0012-365X(77)90164-9
9. Antonio Restivo, Sergio Salemi, Tecla Sportelli, 'Completing codes', RAIRO – Theoretical Informatics and Applications 23 (1989) 135–147. DOI: 10.1051/ita/1989230201351, https://doi.org/10.1051/ita/1989230201351
10. Nguyen Huong Lam, 'Hajós factorizations and completion of codes', Theoretical Computer Science 182 (1997) 245–256. DOI: 10.1016/S0304-3975(97)00032-7, https://doi.org/10.1016/S0304-3975(97)00032-7
11. Liang Zhang, Kar-Ping Shum, 'Finite maximal codes and triangle conjecture', Discrete Mathematics 340 (2017) 541–549. DOI: 10.1016/j.disc.2016.10.008, https://doi.org/10.1016/j.disc.2016.10.008
12. Sándor Szabó, 'Completing codes and the Rédei property of groups', Theoretical Computer Science 359 (2006) 449–454. DOI: 10.1016/j.tcs.2006.02.002, https://doi.org/10.1016/j.tcs.2006.02.002
13. Jean Berstel, Dominique Perrin, Christophe Reutenauer, 'Codes and Automata', Encyclopedia of Mathematics and its Applications 129, Cambridge University Press, 2009. ISBN 978-0-521-88831-8, DOI: 10.1017/CBO9781139195768, https://doi.org/10.1017/CBO9781139195768