Open Problem 4 has been partialy solved by John Nicol. See Further remarks on separating words, Arxiv preprint arXiv:2608.30928 [cs.FL], August 31 2026. Open Problem 5 (separation of two words compared to separation of their reversals) was solved by F. Ebrahimnejad, On the gap between separating words and separating their reversals, Theoretical Computer Science 711 (2018) 79-91.
Open Problem 6 (Bucher's problem for context-free languages) was solved in September 2026 by Rastko Maslic, using an LLM, and there is a forthcoming joint paper with JOS.
Open Problem 8 (sequence on 3 real numbers with all shifted Hankel determinants nonzero) was solved by Claudemir de Souza Cavalcante on July 31 2026, using an LLM. See his preprint A Verified Dakota Number-Wall Certificate for Nonvanishing Shifted Hankel Determinants. But the much more interesting variant for 3 or 4 integers is still unresolved.
Open Problem 14 (state complexity of star-complement-star) was solved by Galina Jirásková. See The state complexity of star-complement-star, DLT 2012, pp. 380-391.
Open Problem 15 (state complexity of boundary) was solved by Jozef Jirásek and Galina Jirásková, On the boundary of regular languages, Theoret. Comput. Sci. 578 (2015), 42-57.
The current best bounds for Open Problem 16 (Pierce expansions) are by Zachary Chase and Mayank Pandey, On the length of Pierce expansions, arxiv preprint arXiv:2211.08374 [math.NT], November 15 2022.
Update: The bound in Open Problem 1 (separating words) has been improved to about n1/3 by Zachary Chase in arXiv:2007.12097 [math.CO]. Also see Chase, Separating words and trace reconstruction, STOC 2021, pp. 21-31.
Open Problem 4 has been partialy solved by John Nicol. See Further remarks on separating words, Arxiv preprint arXiv:2608.30928 [cs.FL], August 31 2026. Open Problem 5 (separation of two words compared to separation of their reversals) was solved by F. Ebrahimnejad, On the gap between separating words and separating their reversals, Theoretical Computer Science 711 (2018) 79-91.
Open Problem 7 (subword complexity of Thue-Morse indexed by the squares) was solved by Yossi Moshe, On the subword complexity of Thue-Morse polynomial extractions, Theoret. Comput. Sci. 389 (2007), 318-329.
Open Problem 8 (infinitely many primes p with tp = 0) has been solved by C. Mauduit and J. Rivat, Sur un problème de Gelfond: la somme des chiffres des nombres premiers, Ann. of Math. (2) 171 (2010), no. 3, 1591-1646.
Open Problem 9 (uniqueness of Thue-Morse partition) was solved (negatively) by Richard Stong. See Joe Buhler, Shahar Golan, Rob Pratt, and Stan Wagon, Littlewood polynomials, spectral-null codes, and equipowerful partitions, Math. Comp. 90 (2021), 1435-1453. Stong's construction, reported as their Theorem 7.1, gives a partition of {0,1,...,251 - 1} for which the power sums vanish for 0 ≤ j < 51, but also for j = 51. So the difference in this problem is 0, but the Thue-Morse partition gives a difference of 51!·21275.
Open Problem 10 (sequence on 3 real numbers with all shifted Hankel determinants nonzero) was solved by Claudemir de Souza Cavalcante on July 31 2026, using an LLM. See his preprint A Verified Dakota Number-Wall Certificate for Nonvanishing Shifted Hankel Determinants. But the much more interesting variant for 3 or 4 integers is still unresolved.
The upper bound for Open Problem 16 (Pierce expansions) was improved slightly by Zachary Chase and Mayank Pandey, On the length of Pierce expansions, arxiv preprint arXiv:2211.08374 [math.NT], November 15 2022.
