Important Open Problems

At the Oberwolfach meeting on Combinatorics on Words in 2010, the participants suggested a list of 18 important open problems in the field. In February 2018, it was updated to include some recent progress on these problems.

Here is the list:

1. Is Π Normal?

2. Frequencies in the Kolakoski word

3. Word Equation Satisfiability

4. Largest Independent System of Word Equations

5. Fraenkel's Problem

6. Brzozowski's Conjecture

7. Enumeration of Squarefree Words

8. Does there exist a k-avoidable word?

9. Is the language of primitive words context-free?

10. Is PCP(3) Decidable?

11. Nivat's Conjecture

12. Reconstruction from subwords

13. The Brown-Freedman-Halbeisen-Hungerbühler-Pirillo-Varricchio Problem

14. The S-adic conjectures

15. Do Codes have unique primitive roots?

16. Is the exponent of a morphism computable?

17. Can we decide if a set of matrices generates the free group?

18. The number of right special factors

-- JeffreyShallit - 13 Oct 2010