Recent Changes in CoWiki Web retrieved at 11:41 (GMT)
Statistics for CoWiki Web Month: Topic views: Topic saves: File uploads: Most popular topic views: Top contributors for topic save...
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...
.displaymath { font style:italic; padding:20px; border:dotted 1px #cccccc; } .rm { font style:normal; } .references { font style:italic; } Equality Languages The...
Let w be an infinite word generated (by iteration) by a given morphism. Let p be any rational number. If there exists a word u such that up is a factor of...
Is there a positive integer n 2 and words u1, u2, ..., un such that both equalities (u1u2 un)2 u12u22 un2, (u1u2 un)3 u13u23 un3 hold simultaneously...
Fraenkel`s problem: A word is balanced if the number of occurrences of any letter in any two factors of equal length differ at most by 1. Given a k letter alphabet...
The subword complexity of an infinite word w is the function that sends each non negative integer n to the number of distinct factors of length n . Note: this...
Is Pi; Normal? A real number x is normal to base b if all finite words w over the alphabet {0,1, ..., b 1} occur as factors of the base b expansion of x with...
A finite word w is primitive if it is not a nontrivial power of another word, that is, if w uk for k 1 implies that k 1. Is the set of all primitive...
Nivat`s conjecture: Consider 2 dimensional words, that is, sets of letters indexed by Z2. Is the following conjecture true? If the number of distinct m ...
The Brown Freedman Halbeisen Hungerb...
Is a given word k avoidable? A word x is called k avoidable if there exists an infinite word w over a k letter alphabet such that no morphic image of x occurs...
Does every code have a unique primitive root? A set of words L is a code if every word has at most one factorization over L . For two languages L and R of words...
What is the number of square free words? A word has a square if it contains two consecutive occurrences of the same factor. For an alphabet of size k 3, we ask for...
The Kolakoski word can be defined in a number of different ways, but probably the simplest is as the unique infinite word k over the alphabet {1, 2}, starting with...
.displaymath { font style:italic; padding:20px; border:dotted 1px #cccccc; } .rm { font style:normal; } .references { font style:italic; } Binary Equality Languages...
Welcome to the home of CoWiki. This is a web based collaboration area for Combinatorics on Words. If you are a UW person, you can register here. Otherwise, if you...
Patterns can be generalized by adding functional dependencies between variables. Here, we consider involutions , that is, ( ( a )) a for all letters a , and...
Avoiding powers Avoiding abelian powers Avoiding patterns under involution StepanHolub 10 Mar 2012
Abelian squares are avoidable over four letter alphabet as shown by V. Ker...
Abelian squares Abelian cubes StepanHolub 10 Mar 2012
`Dejean Conjecture` Thue Morse Word Fibonacci Word StepanHolub 10 Mar 2012
Here are some additional open problems in combinatorics on words: Growth Rate of Power Free Languages Restivo`s Conjecture Local and global periods...
Is PCP(3) decidable? The Post correspondence problem for lists of k words, called PCP(k), asks for a given set {(u1 , v1 ), . . . , (uk , vk )} of k pairs of words...
A word w is said to be morphically imprimitive if there is a non identity morphism f fixing it, that is, f(w) w . Otherwise (that is, if it is fixed only trivially...
Every nonempty word w has a unique primitive root. That is, there is a unique primitive word t such that w ti for some i 1. StepanHolub 10 Sep 2011
Two words u and v commute (that is, uv vu ) if and only if they have the same primitive root. This means that there is a primitive word t and integers i,j...
Two nonempty words u and v are called conjugate (by the word z ) if uz zv holds. The situation can be described by the following equivalent conditions:...
Many basic facts, in particular combinatorial lemmas, are repeated in many papers. This page tries to collect most important facts that can be considered as commonly...
Periodicity Lemma, very often called the `Fine and Wilf theorem`: If a word of length p q GCD(p,q) has periods p and q , then it has also a period GCD(p,q)...
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 deciding the satis #64257;ability of word equations in NP? This question is equivalent to asking whether one can check the correctness of a proposed solution of...
Top Menu of CoWiki Web This topic defines the menu structure of the CoWiki web, used by the TopMenuSkin. 1 Web` Create New Topic...
Let S be a finite set of words over a finite alphabet Sigma;. We say that S is complete if Fact(S ) Sigma; , where Fact(L) denotes the set of all factors of all...
Dejean`s conjecture (now a theorem) states that the largest power avoidable over a k letter alphabet is given by RT(k), and RT(2) 2, RT(3) 7/4, RT(4) 7/5, and...
Reconstruction from subwords of given length: Determine the function f(n) k where k is the smallest integer for which the multiset of (scattered) subwords of...
On the number of right special factors of a word. A factor u of a word w is right special if there exist two distinct letters a and b such that both ua and ub are...
Given two matrices, do they generate the free semigroup? The problem is open even for 2 2 integer matrices. A related result states that it is undecidable whether...
The S adic conjecture: find the correct conditions on a sequence of morphisms so that an in #64257;nite word has linear complexity, if, and only if, it is generated...
A subword w of a given word x is a word that can be obtained by deleting 0 or more symbols from x. It is sometimes called a `scattered subword`. For example, `art...
Brzozowski`s conjecture: Start from any word w, and replace any occurrence uwn x by uwn 1 x or vice versa. Is the resulting language regular? This is easily seen...
A word y is said to be a `factor` of a word w if there exist possibly empty words x, z such that w xyz. For example, `art` is a factor of `Sparta`. Caution should...
CoWiki Web Preferences The following settings are web preferences of the CoWiki web. These preferences overwrite the site level preferences in ., and...
TWiki`s CoWiki web The 1 web of TWiki. TWiki is a Web Based Collaboration Platform for the Enterprise.
RSS feed, ATOM feed, WebNotify, site changes, site map 
Edit | Attach | Topic revision: r1 - 2006-11-15 - TWikiContributor
 |
|
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