A system of word equations is independent if the set of solutions changes when any one equation is removed. Given n > 2, what is the size of the largest independent system of equations over n variables? Or can such a system be arbitrarily large? (It is known it cannot be infinite.) The question is open already for n = 3.

A related question is the analogous question for the size of test sets. For some language L, a test set is a set of words T ⊂ L such that if two morphisms are equivalent on T, then they are equivalent on L. Again, every language over a finite alphabet has a finite test set. A minimal test set is analogous to an independent system of equations. The question is: What is the largest size of a minimal test set for languages over n letters? Is the size limited?

Bounded languages seem to be a good special case to start with. A language is bounded if it is a subset of w₁^*w₂^*...w_k^* for some words w_i. See a particular open problem of this kind

-- JeffreyShallit - 13 Jul 2011

-- StepanHolub - 13 Jul 2011