Recurrence and Subword Complexity in Partial Words

The following implementation provides the user with a way to generate an infinite partial word w of polynomial subword complexity Θ(nα) as well as a completion of w with maximal subword complexity.


1. Choose maximal length N for the subwords of w.

2. Input value for the exponent α, i.e. α = 5/4, α = 1.25, or α= 4, etc.

3. Select "partial word" to generate w or "full word" to generate the completion.

4. Click "Generate" to output the prefix of finite length that contains all distinct subwords up to length N.

5. Select factors or subwords, and input a length n.

6. Click "View" to output the factors or subwords of length n of the infinite word.

Note: The alphabet is A={a,b} and ^ is the 'hole' symbol.

Oops! It seems like you don't have the latest JRE. You can get it here.