TWiki> CoWiki Web>ImportantOpenProblems>LargestIndependentSystem (2011-08-08, StepanHolub) EditAttach

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 *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*_{1}^{*}*w*_{2}^{*}...*w*_{k}^{*} for some words *w*_{i}. See a particular open problem of this kind

-- JeffreyShallit - 13 Jul 2011

-- StepanHolub - 13 Jul 2011

Topic revision: r4 - 2011-08-08 - StepanHolub

Copyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.

Ideas, requests, problems regarding TWiki? Send feedback

Ideas, requests, problems regarding TWiki? Send feedback