The embedding problem for the class of strong alt-induced codes: maximal extensions preserving regularity and finiteness

A strong alt-induced code is a code of the form $Z=XY$ induced by a strong alternative code, equivalently (by the Hien–Van characterization) a product where $X$ is a prefix code, $Y$ is a suffix code, and $XY$ is a code. Ngo Thi Hien's 2018 note solved the embedding problem for such codes only within the prefix, suffix, and bifix subclasses: every regular (resp. finite) prefix, suffix, or bifix strong alt-induced code embeds in a regular maximal one, and finite maximal extensions exist under a classical 'nice' bifix condition. The note explicitly poses, as future work, the embedding problem for the unrestricted class of strong alt-induced codes: whether every regular (resp. finite) strong alt-induced code is contained in a strong alt-induced code that is maximal within the class while preserving regularity (resp. with a regular, or under characterized conditions a finite, maximal extension). No resolution of this question is known in the literature, and the problem remains open.

Background

In the theory of length-variable codes, a code over a finite alphabet $A$ is a language $X \subseteq A^+$ , where $A^+$ denotes the set of non-empty words over $A$ , in which every word admits at most one factorization into elements of $X$ (unique decodability); a code is maximal over $A$ if it is not properly contained in any other code over $A$ . For a class $C$ of codes, a member of $C$ is maximal in $C$ if it is contained in no other member of $C$ . The embedding problem for a class $C$ asks whether every code in $C$ is contained in a code maximal in $C$ , ideally within a well-behaved subfamily such as the finite or the regular (recognizable) languages. Classical results give positive answers for prefix codes (no word of the code is a proper prefix of another): every regular prefix (suffix, bifix) code lies in a maximal regular one, and every finite prefix (suffix) code lies in a finite maximal one with the same maximal word length; for finite bifix codes (both prefix and suffix), finite maximal extensions exist exactly under the classical sufficient/nice conditions expressed through the indicator function of the code (the function counting, for each word, the number of its factorizations into code elements), and in general only a regular maximal extension is guaranteed.

Alternative codes, first introduced by P. T. Huy and coauthors in 2004 within the Vietnamese school of formal language theory, extend this framework: a pair $(X,Y)$ of non-empty subsets of $A^+$ is an alternative code if no word of $A^+$ admits two different 'similar' alternative factorizations, i.e. factorizations $u_1 u_2 \cdots u_n$ that alternate between $X$ and $Y$ and both begin (and both end) in the same set $X$ or $Y$ . The product $XY$ of an alternative code is then an ordinary code, said to be induced by $(X,Y)$ , or an alt-induced code. A strong alternative code is an alternative code $(X,Y)$ satisfying $X^{-1}(XY) \subseteq Y$ and $(XY)Y^{-1} \subseteq X$ (where $w^{-1}Z$ denotes left quotients, extended to sets), and a strong alt-induced code is a code generated by one. Ngo Thi Hien and Do Long Van (2018) introduced these notions and proved the basic characterization: $Z=XY$ is a strong alt-induced code if and only if $X$ is a prefix code, $Y$ is a suffix code, and $XY$ is a code. They also characterized when such a $Z$ is a prefix, suffix, or bifix (or maximal such) code in terms of $X$ and $Y$ — for example, $XY$ is a bifix strong alt-induced code if and only if both $X$ and $Y$ are bifix codes.

Ngo Thi Hien's note 'On strong alt-induced codes' (2018) contributes three things to this program: a cubic-time algorithm deciding whether a given regular code is strong alt-induced; closure of many subclasses of alt-induced codes under concatenation; and a positive solution of the embedding problem for the prefix, suffix, and bifix subclasses — every regular prefix (suffix, bifix) strong alt-induced code is contained in a regular maximal one, and every finite one is contained in a regular maximal one, with a finite maximal extension available whenever the relevant factor satisfies the classical 'nice' bifix condition. These proofs run entirely through the subclass characterization above, by extending the factors $X$ and $Y$ separately to maximal codes of the appropriate kind. That lemma-by-lemma engine has no analogue for the class of all strong alt-induced codes, where no constraint ties the factors to the prefix/suffix/bifix hierarchy, and even chain-closure of the class (needed for a Zorn-type existence argument) is not established. The note therefore closes by explicitly posing the embedding problem for the classes of strong alt-induced codes, beyond the treated subclasses, as future work.

Problem Statement

Solve the embedding problem for the class of strong alt-induced codes over a finite alphabet $A$ (codes $Z = XY$ where $X$ is a prefix code, $Y$ is a suffix code, and $XY$ is a code, equivalently codes induced by strong alternative codes), beyond the prefix, suffix, and bifix subclasses for which the source note already gave a positive solution. Concretely: (a) Regular case — determine whether every regular strong alt-induced code over $A$ is contained in a strong alt-induced code that is maximal within the class of strong alt-induced codes over $A$ and is itself regular; (b) Finite case — determine whether every finite strong alt-induced code is contained in a regular strong alt-induced code maximal within the class (this clause is the restriction of (a) to finite inputs, since every finite language is regular), and determine whether every finite strong alt-induced code is contained in a finite maximal one (as in the bifix subclass, where in general only containment in a regular maximal one is guaranteed and finite maximal extensions exist under the classical 'nice' bifix condition). The same questions may also be posed for the further subclasses of strong alt-induced codes: infix (no codeword is a contiguous factor of another), p-infix and s-infix (no codeword is a contiguous factor of a proper prefix, respectively proper suffix, of another), subinfix, p-subinfix and s-subinfix (no codeword is a scattered subword of a proper infix, respectively proper prefix, respectively proper suffix, of another), and hyper (no codeword is a scattered subsequence of another), per the source's phrasing 'the embedding problem for the classes of strong alt-induced codes'.

References

Ngo Thi Hien, 'On strong alt-induced codes', Applied Mathematical Sciences 12(7):327–336 (2018). DOI: 10.12988/ams.2018.8113; arXiv:1801.02603. https://doi.org/10.12988/ams.2018.8113 (https://arxiv.org/abs/1801.02603)
Ngo Thi Hien and Do Long Van, 'Codes induced by alternative codes', Acta Mathematica Vietnamica 43:357–371 (2018). DOI: 10.1007/s40306-018-0247-2; arXiv:1801.02598. https://doi.org/10.1007/s40306-018-0247-2
Ngo Thi Hien, 'B-Codes and their relationship with alternative codes', Journal of Computer Science and Cybernetics 33(3):263–271 (2017). DOI: 10.15625/1813-9663/33/3/10919. https://doi.org/10.15625/1813-9663/33/3/10919
Ngo Thi Hien, 'Characterizations for several classes of alternative codes', Journal of Computer Science and Cybernetics 32(3):273–283 (2016). DOI: 10.15625/1813-9663/32/3/9350. https://doi.org/10.15625/1813-9663/32/3/9350