Finite completions of codes within structured families: θ-invariant codes and strong alt-induced codes

The embedding problem for a class C of variable-length codes asks whether every member of C that is finite (or regular) is contained in a member of C that is maximal or complete within C while remaining finite (or regular). In the classical unrestricted setting, Ehrenfeucht and Rozenberg proved every regular code embeds into a maximal regular code, while Restivo constructed finite codes that are contained in no finite complete code; even the question of whether every three-word code has a finite completion remains open as of 2025. This task concerns the family-level version of the finite-completion question for structured code families. The submonoid instance is already resolved (Néraud proved the prefix case decidable in 2006 and characterized the circular case via synchronizing words in 2008), leaving two documented-open instances: (1) Néraud and Selmi embed every non-complete θ-invariant code into a complete one, but the completion is generally infinite, and they leave open which finite θ-invariant codes admit finite complete θ-invariant completions, with an explicit undecided example; (2) the embedding problem for strong alt-induced codes is solved only for the prefix, suffix, and bifix subclasses. The problem asks to characterize finite completability in both families: for θ-invariant codes, give the general characterization of which finite codes admit a finite complete θ-invariant completion, decide the published open example, and settle the existence of θ-invariant analogues of Restivo's non-finitely-completable codes; for strong alt-induced codes, solve the embedding problem for the full class.

Background

Fix a finite alphabet $A$; the free monoid $A^{*}$ is the set of all finite words over $A$ under concatenation, $A^{+}$ the nonempty words, and $F(X)$ the set of factors (infixes) of words of $X\subseteq A^{*}$. A set $X\subseteq A^{+}$ is a (variable-length) code when every word of the submonoid $X^{*}$ it generates factors in exactly one way over $X$, so that messages encoded by concatenating codewords are uniquely decipherable. A code is prefix (suffix) if no codeword is a proper prefix (suffix) of another, and bifix if both hold. A code is complete if every word of $A^{*}$ lies in $F(X^{*})$, and maximal if no proper superset is a code. A code is thin if some word of $A^{*}$ is not a factor of any of its words (every finite or regular code is thin); for thin codes maximality coincides with completeness, a classical theorem recorded by Berstel, Perrin, and Reutenauer. Two classical facts delimit the finite-completion landscape. Positively, Ehrenfeucht and Rozenberg (1986) showed every regular code is included in a maximal regular code, and Bruyère, Wang, and Zhang (1990) handled codes with finite deciphering delay (codes whose decoding delay is bounded by a fixed number of codewords). Negatively, Restivo (1977), using factorizations of cyclotomic polynomials, constructed finite codes contained in no finite complete code at all, so finite completion can fail; which finite codes admit finite completions is still unsettled at a remarkably fine granularity — as of 2025 it remains a famous open question whether every three-word code has a finite completion (Cao et al. 2025). This task concerns the family-level version of that question. For a class $C$ of codes, the embedding problem for $C$ asks whether every code $X\in C$ that is finite (or regular) is included in a code $Y\in C$ that is maximal in $C$ — or complete, where completeness is the relevant density notion — while $Y$ still satisfies the same finiteness (or regularity) property. Three instances of this problem arise; the submonoid instance is resolved and the two family instances below remain open. Family 1 (open): θ-invariant codes. Let $\theta$ be a non-identity literal (anti-) automorphism of $A^{*}$ (that is, $\theta\neq id_{A^{*}}$, equivalently of order greater than $1$): a mapping determined by a permutation of the alphabet, extended to words letterwise, possibly composed with reversal (an antimorphism), the basic example being the mirror map. A language $L$ is θ-invariant if $\theta(L)\subseteq L$; such symmetry requirements arise in DNA word computing, where $\theta$ models the Watson–Crick involution, and in pseudopalindrome combinatorics. Néraud and Selmi (published version 2020) proved that every non-complete θ-invariant code embeds into a complete θ-invariant code and that maximality and completeness agree for thin θ-invariant codes; however, their embedding is generally infinite, and they exhibit finite θ-invariant codes with no finite complete prefix or bifix θ-invariant completion while leaving the general finite question undecided. Family 2 (open): strong alt-induced codes. For $U,V\subseteq A^{*}$ write $U^{-1}V$ for the set of words obtained by deleting from a word of $V$ a prefix belonging to $U$, and dually $VU^{-1}$ for the set of words obtained by deleting from a word of $V$ a suffix belonging to $U$. A pair $(X,Y)$ of nonempty subsets of $A^{+}$ is an alternative code if no word of $A^{+}$ admits two distinct similar alternative factorizations, i.e., two different factorizations alternating between blocks of $X$ and $Y$ that both begin and end with blocks from the same set; it is a strong alternative code if additionally $X^{-1}(XY)\subseteq Y$ and $(XY)Y^{-1}\subseteq X$. A code $Z$ is alt-induced if $Z=XY$ for some alternative code $(X,Y)$, and strong alt-induced if $(X,Y)$ may be chosen strong; this hierarchy, introduced by D. L. Van and coauthors in the framework of codes defined by binary relations, refines the prefix code hierarchy. Ngo Thi Hien (2018) gave a cubic-time algorithm deciding whether a regular code is strong alt-induced, and solved the embedding problem for prefix, suffix, and bifix strong alt-induced codes in both the finite and the regular case, explicitly leaving the full class open. Family 3 (resolved): completions inside submonoids of $A^{*}$, where Néraud proved decidability for prefix codes (2006) and a synchronizing-word characterization for circular codes (2008); a circular code is one whose codewords allow unique decipherment when messages are read on a circle, i.e., every word obtained by concatenating codewords has unique factorization up to cyclic shift.

Problem Statement

Solve the embedding problem, in the forms that remain open, for two structured classes of variable-length codes, each documented as open in the cited literature: for θ-invariant codes only the finite form remains open (the regular form is settled by Néraud and Selmi 2020, who construct a regular complete θ-invariant completion when $A$ is finite and the input code is regular), while for strong alt-induced codes both the finite and the regular forms remain open. The common objective is to extend the classical finite-completion theory of unrestricted codes to families where the completion must stay inside the family: determine, for each family below, exactly which finite members admit completions that are simultaneously complete or maximal, inside the family, and still finite (and, for regular inputs, still regular). Neither family subsumes the other; the two instances share the common embedding-problem objective but involve different structure, symmetry versus decomposition. (1) θ-invariant codes: let $A$ be a finite alphabet and $\theta$ a non-identity literal (anti-)automorphism of $A^{*}$ (thus $\theta\neq id_{A^{*}}$), i.e., the letterwise extension of a permutation of $A$, possibly composed with reversal; a code $X$ is θ-invariant if $\theta(X)\subseteq X$ and complete if $F(X^{*})=A^{*}$. Characterize which finite θ-invariant codes $X$ are contained in a finite complete θ-invariant code. This general characterization is the target; the two corollaries below must also be answered: (a) decide whether $X=\{aa,b\}$ over $A=\{a,b\}$, with $\theta$ the mirror antimorphism, is contained in any finite complete θ-invariant code (Example 10 of Néraud and Selmi 2020, explicitly left undecided: no finite complete prefix or bifix θ-invariant completion exists, while the infinite regular $\{b\}\cup\{ab^{n}a:n\ge 0\}$ is one); and (b) determine whether θ-invariant analogues of Restivo's 1977 construction exist, that is, whether there is a finite θ-invariant code contained in no finite complete θ-invariant code. (2) Strong alt-induced codes: determine whether every finite (respectively regular) strong alt-induced code $Z=XY$, with $(X,Y)$ a strong alternative code, is contained in a maximal finite (respectively maximal regular) strong alt-induced code, and characterize which finite strong alt-induced codes admit such finite completions within the class; the prefix, suffix, and bifix subclasses are already settled, so the target is the full class. In each family the target is the general characterization of which finite members admit completions within the family.

References

1. A. Ehrenfeucht and G. Rozenberg, 'Each regular code is included in a maximal regular code', RAIRO - Theoretical Informatics and Applications 20 (1986) 89-96. DOI: 10.1051/ita/1986200100891, https://doi.org/10.1051/ita/1986200100891
2. V. Bruyère, L. Wang, and L. Zhang, 'On Completion of Codes with Finite Deciphering Delay', European Journal of Combinatorics 11 (1990) 513-521. DOI: 10.1016/S0195-6698(13)80036-4, https://doi.org/10.1016/S0195-6698(13)80036-4
3. A. 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
4. A. Restivo, S. Salemi, and T. Sportelli, 'Completing codes', RAIRO - Theoretical Informatics and Applications 23 (1989) 135-147. DOI: 10.1051/ita/1989230201351, https://doi.org/10.1051/ita/1989230201351
5. J. Berstel, D. Perrin, and C. Reutenauer, 'Codes and Automata', Cambridge University Press, 2009. DOI: 10.1017/CBO9781139195768, https://doi.org/10.1017/CBO9781139195768
6. J. Néraud and C. Selmi, 'Free monoid theory: maximality and completeness in arbitrary submonoids', International Journal of Algebra and Computation 13(5) (2003) 507-516. DOI: 10.1142/S0218196703001584, https://doi.org/10.1142/S0218196703001584
7. J. Néraud, 'Completing prefix codes in submonoids', Theoretical Computer Science 356 (2006) 245-254. DOI: 10.1016/j.tcs.2006.01.027, https://doi.org/10.1016/j.tcs.2006.01.027
8. J. Néraud, 'Completing circular codes in regular submonoids', Theoretical Computer Science 391 (2008) 90-98. DOI: 10.1016/j.tcs.2007.10.033, https://doi.org/10.1016/j.tcs.2007.10.033
9. J. Néraud and C. Selmi, 'Embedding a θ-invariant code into a complete one', Theoretical Computer Science 806 (2020) 28-41; preprint arXiv:1801.05164 (2018). DOI: 10.1016/j.tcs.2018.08.022, https://arxiv.org/abs/1801.05164
10. Ngo Thi Hien, 'On strong alt-induced codes', Applied Mathematical Sciences 12(7) (2018) 327-336; preprint arXiv:1801.02603. DOI: 10.12988/ams.2018.8113, https://doi.org/10.12988/ams.2018.8113
11. J. Néraud, 'When Variable-Length Codes Meet the Field of Error Detection', 9th International Conference on Algebraic Informatics (CAI 2022), Lecture Notes in Computer Science 13706, Springer (2022) 203-222; preprint arXiv:2208.14681. DOI: 10.1007/978-3-031-19685-0_15, https://doi.org/10.1007/978-3-031-19685-0_15
12. J. Néraud, 'Topologies for error-detecting variable-length codes', Information and Computation 295 (2023) 105092; preprint arXiv:2309.01997. DOI: 10.1016/j.ic.2023.105092, https://doi.org/10.1016/j.ic.2023.105092
13. C. Cao, L. Liao, Z. Yan, D. Yang, and Y. Yuan, 'Three-word codes {a, aba, u} and {a, ab, v} having finite completions', Acta Informatica 62(2) (2025). DOI: 10.1007/s00236-025-00487-x, https://doi.org/10.1007/s00236-025-00487-x
14. Ngo Thi Hien, 'B-Codes and their relationship with alternative codes', Journal of Computer Science and Cybernetics 33(3) (2018) 263-271. DOI: 10.15625/1813-9663/33/3/10919, https://doi.org/10.15625/1813-9663/33/3/10919