Schützenberger's maximal-code commutative equivalence conjecture

Let CC be a finite uniquely decodable code over the binary alphabet {a,b}\{a,b\}. A code is maximal if, for every word w{a,b}<NCw\in\{a,b\}^{<\mathbb{N}}\setminus C, the set C{w}C\cup\{w\} is not a code. Two codes are commutatively equivalent if there is a bijection between them preserving the numbers of aa's and bb's in corresponding words. A code is prefix-free if no codeword is a proper prefix of another.

Schützenberger's conjecture. Every maximal code is commutatively equivalent to a prefix-free code.

The conjecture is presented as a restricted version of the disproved unrestricted conjecture. The supplied text does not provide a resolution of this maximal-code version; its status is therefore left open.

Sources & referencesView supporting material

Primary source

Dean Kraizberg, “A Weak Structural Form of Commutative Equivalence in Finite Codes”, arXiv:2603.27656 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.