Abelian squares are avoidable over four letter alphabet as shown by V. Keränen in V. Keränen, Abelian squares are avoidable on 4 letters , Proc. ICALP `92, Lecture ...

Here are some additional open problems in combinatorics on words: Growth Rate of Power Free Languages Restivo`s Conjecture Local and global periods ...

Avoiding powers Avoiding abelian powers Avoiding patterns under involution StepanHolub 10 Mar 2012

Abelian squares Abelian cubes StepanHolub 10 Mar 2012

Patterns can be generalized by adding functional dependencies between variables. Here, we consider involutions , that is, ( ( a )) a for all letters a , and ...

`Dejean Conjecture` Thue Morse Word Fibonacci Word StepanHolub 10 Mar 2012

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 ...

.displaymath { font style:italic; padding:20px; border:dotted 1px #cccccc; } .rm { font style:normal; } .references { font style:italic; } Binary Equality Languages ...

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 ...

Does every code have a unique primitive root? A set of words L is a code if any word has at most one factorization over L. For two languages L and R of words, we ...

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: ...

.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 in #64257;nite 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 ...

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 ...

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 ...

Fraenkel`s problem: A word is balanced if the number of occurences of any letter in any two factors of equal length differ at most by 1. Given a k letter alphabet ...

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 ...

The Halbeisen Hungerb hler Pirillo Varricchio problem asks, is there an infinite word over a finite subset of N, the non negative integers, containing no two consecutive ...

Important Open Problems At the Oberwolfach meeting on Combinatorics on Words in 2010, the participants suggested a list of important open problems in the field. Here ...

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 limiting ...

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 ...

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 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 ...

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 ...

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 n blocks ...

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 ...

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 ...

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) ...

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

A 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 words over {0 ...

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 ...

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 ...

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 ...

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 ...

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 ...

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 function ...

TWiki`s CoWiki web The 1 web of TWiki. TWiki is a Web Based Collaboration Platform for the Enterprise.

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 ...

Web Web Home Changes Index Search Webs

This is a subscription service to be automatically notified by e mail when topics change in this CoWiki web. This is a convenient service, so you do not have to ...

CoWiki Web Preferences The following settings are web preferences of the CoWiki web. These preferences overwrite the site level preferences in ., and ...

/CoWiki The 1 web of TWiki. TWiki is a Web Based Collaboration Platform for the Enterprise.

Statistics for CoWiki Web Month: Topic views: Topic saves: File uploads: Most popular topic views: Top contributors for topic save ...

Top Menu of CoWiki Web This topic defines the menu structure of the CoWiki web, used by the TopMenuSkin. 1 Web` Create New Topic ...

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 ...

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 in ...

Number of topics: 53

See also the faster WebTopicList

Edit | Attach | Print version | History: r1 | Backlinks | Raw View | Raw edit | More topic actions

Topic revision: r1 - 2006-11-15 - TWikiContributor

Copyright © 2008-2018 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