(r1) LargestIndependentSystem < CoWiki

CoWiki Web>ImportantOpenProblems>LargestIndependentSystem (revision 1) (raw view)~~EditAttach~~

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

A system of word equations is independent if the set of solutions changes when any one 
equation is removed. Given <i>n</i> > 2, what is the size of the largest independent system of equations over <i>n</i> variables? 

A related question is the analogous question for the size of test sets. For some language <i>L</i>, a test set is a set of words <i>T</i> &subset; <i>L</i> such that, if two morphisms are equivalent on <i>T</i>, then they are 
equivalent on <i>L</i>. What is the size of test sets for bounded languages? 


-- Main.JeffreyShallit - 13 Jul 2011

Topic revision: r1 - 2011-07-13 - JeffreyShallit

CoWiki

CoWiki Web
CoWiki Web Home
Changes
Index
Search

Webs
- AIMAS
- CERAS
- CF
- CoWiki
- CrySP
- External
- Faqtest
- HCI
- Himrod
- ISG
- Main
- Multicore
- Sandbox
- TWiki
- TestNewSandbox
- TestWebS
- UW

My links
- People
- CERAS
- WatForm
- Tetherless lab
- Ubuntu Main.HowTo
- eDocs
- RGG NE notes
- RGG
- CS infrastructure
- Grad images

Edit