Completing codes with bounded deciphering delay inside submonoids of the free monoid

For a submonoid $M$ of the free monoid $A^*$, a code $X\subseteq M$ is weakly $M$-complete when every word of $M$ occurs as a factor of some word of $X^*$. Néraud's series of papers (2003–2008) built a completion theory inside submonoids: prefix codes were fully settled with decidable criteria and regularity-preserving constructions (TCS 2006), and, for regular $M$, the embeddability of a regular circular code into a weakly $M$-complete one was characterized by the existence of a synchronizing word in the minimal automaton of $M$ (TCS 2008). The bounded-deciphering-delay analogue of that program's instance-wise completion question is to characterize when a delay code $X\subseteq M$ embeds into a weakly $M$-complete code of bounded delay inside $M$, and to decide this effectively when $M$ and $X$ are regular (or $X$ is finite).

Background

Let $A$ be a finite alphabet and $A^*$ the free monoid of all words over $A$ (with concatenation and empty word $\varepsilon$). A subset $X\subseteq A^*$ is a (variable-length) code if every word of the submonoid $X^*$ generated by $X$ admits a unique factorization over $X$; a prefix code is a code no element of which is a proper prefix of another. A code $X$ has deciphering delay $d\ge 0$ if any two distinct codewords $x,x'\in X$ satisfy $xX^dA^*\cap x'X^*=\varnothing$; equivalently, once a decoder reading a message from left to right has tentatively parsed a codeword followed by $d$ further codewords, no other codeword can start a valid parsing of the same prefix, so the decoder can safely commit to the first codeword. The delay of $X$ is the least such $d$, and it may be infinite; codes with finite deciphering delay (also called bounded deciphering delay) form a classical family strictly between prefix codes (delay exactly $0$) and general codes. A circular code is a code over which every word written on a circle has at most one decomposition, so that any concatenation of codewords remains uniquely decodable under cyclic shifts of the cutting point. A language is regular if it is recognized by a finite automaton; its minimal automaton is the canonical smallest deterministic recognizer. A word $w$ is synchronizing for an automaton if reading $w$ maps all states to a single state. For a language $L$, $P(L)$ denotes the set of prefixes of words of $L$.

In the classical setting $M=A^*$, completion is well understood: every regular (resp. finite) prefix code can be embedded into a regular (resp. finite) prefix code that is complete in $A^*$, every regular code is included in a maximal regular code (Ehrenfeucht and Rozenberg, 1986), and finite codes with finite deciphering delay admit finite completions of finite delay (Bruyère, Wang, Zhang, 1990). By contrast, whether every finite code — even every three-word code — can be embedded into a finite maximal code is a famous problem of code theory that is still open (restated as open by Cao, Liao, Yan, Yang, and Yuan, 2025).

Néraud and Selmi transplanted these questions to an arbitrary submonoid $M\subseteq A^*$, modeling a constrained channel or subset of admissible messages: $X\subseteq M$ is weakly $M$-complete if every word of $M$ is a factor of some word of $X^*$, and one asks whether $X$ can be extended to a weakly $M$-complete code $\hat X$ with $X\subseteq\hat X\subseteq M$, preserving structural properties of $X$ (regularity, finiteness, prefix property, circularity, delay). Their program established: maximality and completeness basics for arbitrary submonoids (2003); a characterization of submonoids admitting a finite $M$-complete prefix code, namely $M^{-1}M\subseteq P(M)$, equivalently $(M\setminus MA^+)\setminus\{\varepsilon\}$ being a finite $M$-complete prefix set (2004); an effective general completion formula for submonoids of finite rank — the rank of a submonoid $M$ being the least integer $r$ such that some word maps the whole state set of the minimal automaton of $M$ onto exactly $r$ states, so that every regular submonoid has finite rank — a formula which preserves regularity (2005–2006); a full decidable theory for prefix codes, namely that for a regular submonoid $M$ and a regular or finite prefix code $X\subseteq M$ it is decidable whether a weakly $M$-complete regular (resp. finite) prefix code containing $X$ exists (2006); and, for regular $M$, a characterization of when a regular circular code $X\subseteq M$ embeds into a weakly $M$-complete one — precisely when the minimal automaton of $M$ has a synchronizing word — together with a study of uniformly synchronous codes (2008). What no work in this line or after it addresses is the remaining classical code family: codes with bounded deciphering delay.

Problem Statement

Within Néraud's framework of weak $M$-completeness — $X\subseteq M$ is weakly $M$-complete if every word of the submonoid $M$ is a factor of some word of $X^*$ — address the bounded-deciphering-delay analogue of the prefix (2006) and circular (2008) completion questions:

1. Characterization. For a submonoid $M\subseteq A^*$ of finite rank (in particular a regular submonoid) and a code $X\subseteq M$ with finite deciphering delay, give intrinsic conditions on $M$ and $X$ — analogous to the condition $M^{-1}M\subseteq P(M)$ for finite prefix completion and to the synchronizing-word condition for circular completion — that are equivalent to the existence of a weakly $M$-complete code $\hat X$ of finite deciphering delay with $X\subseteq\hat X\subseteq M$.
2. Decidability and construction. When $M$ and $X$ are both regular (or $X$ is finite), decide effectively whether such a completion exists, and construct one when it does; the constructed $\hat X$ should be regular (resp. finite when $X$ is finite) and have finite deciphering delay.

As a secondary residual of the same source question, the same items may be addressed for circular codes when the ambient submonoid is not regular, extending the 2008 theory beyond the regular case.

References

1. Jean Néraud, Completing prefix codes in submonoids, Theoretical Computer Science 356(1-2):245-254, 2006. DOI: 10.1016/j.tcs.2006.01.027, https://doi.org/10.1016/j.tcs.2006.01.027 (HAL record hal-05367090)
2. Jean Néraud, Completing circular codes in regular submonoids, Theoretical Computer Science 391(1-2):90-98, 2008. DOI: 10.1016/j.tcs.2007.10.033, https://doi.org/10.1016/j.tcs.2007.10.033 (HAL record hal-05367054)
3. Jean Néraud, On the completion of codes in submonoids with finite rank, Fundamenta Informaticae 74:549-562, 2006. HAL: https://hal.science/hal-05367119
4. Jean Néraud, Completing a code in a regular submonoid of the free monoid, in Machines, Computations, and Universality (MCU 2004), Lecture Notes in Computer Science 3354:281-291, Springer, 2005. DOI: 10.1007/978-3-540-31834-7_23, https://doi.org/10.1007/978-3-540-31834-7_23
5. Jean Néraud and Carla Selmi, Free monoid theory: maximality and completeness in arbitrary submonoids, International Journal of Algebra and Computation 13(5):507-516, 2003. DOI: 10.1142/S0218196703001584, https://doi.org/10.1142/S0218196703001584
6. Jean Néraud and Carla Selmi, A characterization of complete finite prefix codes in an arbitrary submonoid of A*, Journal of Automata, Languages and Combinatorics 9(1):103-110, 2004. DOI: 10.25596/jalc-2004-103, https://doi.org/10.25596/jalc-2004-103
7. Véronique Bruyère, Limin Wang, Liang Zhang, On completion of codes with finite deciphering delay, European Journal of Combinatorics 11(6):513-521, 1990. DOI: 10.1016/S0195-6698(13)80036-4, https://doi.org/10.1016/S0195-6698(13)80036-4
8. Jean Néraud and Carla Selmi, On codes with a finite deciphering delay: constructing uncompletable words, Theoretical Computer Science 255(1-2):151-162, 2001. DOI: 10.1016/S0304-3975(99)00160-7, https://doi.org/10.1016/S0304-3975(99)00160-7
9. Sujin Shin, Codes and maximal monoids, Theoretical Computer Science 411(16-18):1809-1817, 2010. DOI: 10.1016/j.tcs.2010.01.035, https://doi.org/10.1016/j.tcs.2010.01.035
10. Lila Kari, Stavros Konstantinidis, Steffen Kopecki, On the maximality of languages with combined types of code properties, Theoretical Computer Science 550:79-89, 2014. DOI: 10.1016/j.tcs.2014.07.015, https://doi.org/10.1016/j.tcs.2014.07.015
11. 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 62(2), article 20, 2025. DOI: 10.1007/s00236-025-00487-x, https://doi.org/10.1007/s00236-025-00487-x
12. A. Ehrenfeucht, G. Rozenberg, Each regular code is included in a maximal regular code, RAIRO - Theoretical Informatics and Applications 20(1):89-96, 1986. DOI: 10.1051/ita/1986200100891, https://doi.org/10.1051/ita/1986200100891
13. Jean Néraud, Ten Conferences WORDS: Open Problems and Conjectures, arXiv:1705.04055, 2017, https://arxiv.org/abs/1705.04055
14. Marie-Pierre Béal, Dominique Perrin, Codes and sofic constraints, Theoretical Computer Science 340(2):381-393, 2005. DOI: 10.1016/j.tcs.2005.03.033, https://doi.org/10.1016/j.tcs.2005.03.033