Determine whether the length of the minimal uncompletable word of M is polynomial in l(M), or even in sl(M). It is known that M is a…

Determine whether the length of the minimal uncompletable word of M is polynomial in l(M), or even in sl(M). It is known that M is a variable-length code if for all u_1,...,u_n,v_1,...,v_m \in M, u_1...u_n = v_1...v_m implies n = m and u_i = v_i for all 0 < i \leq n. In such cases, we do not yet know if a polynomial bound exists. This is a possible weakening of the Restivo conjecture (already disproven in general, though upper bounds remain unknown).

Open the “Other problems” section on Wikipedia →

Source: List of unsolved problems in computer science (CC BY-SA 4.0)