Finite completions of theta-invariant codes: which finite theta-invariant codes embed into a finite complete theta-invariant code?

Néraud and Selmi introduced the theory of theta-invariant codes — coding sets stable under a literal (anti-)automorphism theta of the free monoid, motivated by symmetry requirements such as reversal and DNA-style antimorphisms — and proved that every non-complete theta-invariant code embeds into a complete theta-invariant code, which can be taken regular when the starting code is regular. Their construction is, however, necessarily infinite in general, and they explicitly left open the finite version: which finite theta-invariant codes can be embedded into a finite complete theta-invariant code, and whether theta-invariant analogues of Restivo's classical non-finitely-completable codes exist. They highlight one concrete undecided instance: the code X = {aa, b} over the binary alphabet, with theta the mirror image (reversal), which admits no finite complete bifix completion but does admit an infinite regular complete theta-invariant completion. This problem asks for a resolution of the general finite-completion question together with the status of that pinned instance.

Background

Let $A$ be a finite alphabet and $A^*$ the free monoid of all words over $A$ under concatenation. A set $X \subseteq A^*$ is a code if every message in $X^*$ (the set of concatenations of codewords) factors into codewords in a unique way; $X$ is a prefix (resp. suffix) code if no codeword is a proper prefix (resp. suffix) of another, and bifix if it is both. A code $X$ is complete if every word of $A^*$ occurs as a factor (contiguous block) of some message in $X^*$ , and maximal if it is not properly contained in a larger code. A code is thin if some word never occurs as a factor of any codeword; every finite or regular code is thin, and a classical theorem of Schützenberger (recorded in the monograph of Berstel, Perrin and Reutenauer) states that a thin code is maximal if and only if it is complete.

Completing a code is a classical theme. Zorn's lemma embeds any code into a maximal one, and Ehrenfeucht and Rozenberg proved that every regular code is included in a regular maximal (hence complete) one. The finite situation is fundamentally different: Restivo constructed, via factorizations of cyclotomic polynomials, finite codes that cannot be embedded into any finite complete code, and deciding which finite codes admit finite completions has remained a hard question since — even the three-word case is, per recent work of Cao and coauthors (2025), a famous open problem.

Néraud and Selmi [1] transport these questions to theta-invariant codes. Here $\theta$ is a literal (anti-) automorphism of $A^*$ : a bijection determined by a permutation of the alphabet letters, applied either order-preservingly ( $\theta(uv) = \theta(u)\theta(v)$ , an automorphism) or order-reversing ( $\theta(uv) = \theta(v)\theta(u)$ , an antimorphism, e.g. the mirror image that reverses word order while fixing letters, or a DNA-style antimorphism that both swaps letters and reverses). A language $L$ is $\theta$ -invariant if $\theta(L) \subseteq L$ ; for a finite set this means $\theta$ permutes its elements. Such invariance is a strong symmetry requirement on a code, motivated by coding applications where reversal- or complement-symmetric codeword sets are desired.

Néraud and Selmi extend the defect theorem to this setting, give several families of finite complete $\theta$ -invariant codes (uniform codes $A^n$ , bifix constructions, and one non-prefix non-suffix example), and prove two embedding theorems: any non-complete $\theta$ -invariant code embeds into a complete $\theta$ -invariant code, regular whenever the input is regular over a finite alphabet; and for thin $\theta$ -invariant codes, completeness is equivalent to maximality within the family of $\theta$ -invariant codes. However, the completions produced may be genuinely infinite, and the finite analogue fails to follow: under an antimorphism, any finite complete $\theta$ -invariant prefix code must in fact be bifix, and the paper's Example 10 exhibits a finite $\theta$ -invariant bifix code, $X = \{aa, b\}$ with $\theta$ the mirror image over $A = \{a, b\}$ , that provably embeds into no finite complete bifix code whatsoever — hence into no finite complete $\theta$ -invariant prefix code — while it does embed into the infinite regular complete $\theta$ -invariant bifix code $\{b\} \cup \{ab^n a : n \ge 0\}$ . Whether some finite complete $\theta$ -invariant code (necessarily neither prefix nor suffix) contains it is unknown, and the authors state that, as far as they know, the question of embedding a finite $\theta$ -invariant code into a finite complete one remains open. This is precisely the $\theta$ -invariant analogue of Restivo's classical discovery of finite codes with no finite completion.

Problem Statement

Let $A$ be a finite alphabet and let $\theta$ be a literal (anti-) automorphism of the free monoid $A^*$ , i.e., the bijection induced by a permutation of the letters, applied either as an automorphism ( $\theta(uv) = \theta(u)\theta(v)$ ) or as an antimorphism ( $\theta(uv) = \theta(v)\theta(u)$ ). Call a finite $\theta$ -invariant code $X \subseteq A^*$ (a code with $\theta(X) \subseteq X$ ) finitely completable if there exists a finite complete $\theta$ -invariant code $Y$ with $X \subseteq Y$ .

General question (the source's open problem). The source poses the question instancewise: given a finite $\theta$ -invariant code $X$ , can $X$ be embedded into a finite complete $\theta$ -invariant code? In fuller form, determine which finite $\theta$ -invariant codes are finitely completable — by a structural characterization or a decision procedure — and, on the negative side, exhibit $\theta$ -invariant analogues of Restivo's non-finitely-completable codes, i.e., finite $\theta$ -invariant codes contained in no finite complete $\theta$ -invariant code. Two scope notes. (i) The identity map $\theta = id$ is a literal automorphism for which every code is $\theta$ -invariant; with this degenerate choice the question specializes to the classical finite-completion problem, whose universal form "is every finite code finitely completable?" is already answered negatively by Restivo's theorem — so a universal head claim over all $\theta$ is known false, and the open content of the source's question is the full characterization/decision problem (open even in the classical case, e.g. for three-word codes) together with the genuinely invariant cases, the source's own motivating instance being an antimorphism. (ii) Note the asymmetry already established in the source: for a nontrivial automorphism $\theta$ the prefix case is settled positively by tree completion, while for antimorphisms every finite complete $\theta$ -invariant prefix code must be bifix — so the obstruction concentrates in the antimorphism case, and any positive answer there must use codes that are neither prefix nor suffix.

Pinned instance (Example 10 of the source, required subcase). Over $A = \{a, b\}$ with $\theta$ the mirror image ( $\theta(a) = a$ , $\theta(b) = b$ , $\theta(uv) = \theta(v)\theta(u)$ ), does the code $X = \{aa, b\}$ embed into a finite complete $\theta$ -invariant code? It is known that $X$ embeds into no finite complete bifix code (hence into no finite complete $\theta$ -invariant prefix code) and that it embeds into the infinite regular complete $\theta$ -invariant bifix code $\{b\} \cup \{ab^n a : n \ge 0\}$ .

The problem is resolved by determining exactly which finite $\theta$ -invariant codes are finitely completable, via a structural characterization or a decision procedure for finite $\theta$ -invariant completability. A single exhibited non-completable code does not by itself resolve it: Restivo's classical codes, read through $\theta = id$ , already are finite $\theta$ -invariant codes contained in no finite complete $\theta$ -invariant code, while the source's characterization question — including the pinned antimorphism instance below, on which the source records no decision — remains open. Similarly, a general finite construction for some restricted class of $\theta$ -invariant codes is partial progress rather than a resolution. Any resolution must in particular decide the pinned instance.

References

Jean Néraud, Carla Selmi, Embedding a θ-invariant code into a complete one, Theoretical Computer Science 806 (2020) 28–41, DOI 10.1016/j.tcs.2018.08.022, preprint arXiv:1801.05164, https://arxiv.org/abs/1801.05164
Jean Néraud, Carla Selmi, Invariance: A Theoretical Approach for Coding Sets of Words Modulo Literal (Anti)Morphisms, WORDS 2017 (Lecture Notes in Computer Science), DOI 10.1007/978-3-319-66396-8_20, preprint arXiv:1705.05564, https://arxiv.org/abs/1705.05564
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
A. Ehrenfeucht, 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
Jean Berstel, Dominique Perrin, Christophe Reutenauer, Codes and Automata, Cambridge University Press (2009), DOI 10.1017/cbo9781139195768, https://doi.org/10.1017/cbo9781139195768
Chunhua Cao, Lei Liao, Zhongmei Yan, Di Yang, Yuguang Yuan, Three-word codes {a, aba, u} and {a, ab, v} having finite completions, Acta Informatica (2025), DOI 10.1007/s00236-025-00487-x, https://doi.org/10.1007/s00236-025-00487-x
Chunhua Cao, Zhongmei Yan, Yali Yang, Hao Xie, Yingheng Li, Three-Word Codes {a, aba, u} Having a Finite Completion, International Journal of Foundations of Computer Science (published online 13 March 2025), DOI 10.1142/S0129054125500091, https://doi.org/10.1142/S0129054125500091
Jean Néraud, Variable-Length Codes Independent or Closed with respect to Edit Relations, Information and Computation (2021), DOI 10.1016/j.ic.2021.104747, preprint arXiv:2104.14185, https://arxiv.org/abs/2104.14185