What is the size of largest independent system of word equations?

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 TL 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 w1*w2*...wk* for some words wi. See a particular open problem of this kind

-- JeffreyShallit - 13 Jul 2011

-- StepanHolub - 13 Jul 2011

Edit | Watch | Print version | History: r4 < r3 < r2 < r1 | Backlinks | Raw View | More topic actions
Topic revision: r4 - 2011-08-08 - StepanHolub

• Webs