Subword Complexity of Partial Words

The applet below provides an implementation of our algorithm in Java. This page may not function correctly if you do not have Java Runtime Environment v6u14 and the latest Java Plugin.

The subword complexity function of a finite or infinite partial word w over a given alphabet assigns to each positive integer n, the number of distinct full words over the alphabet that are compatible with factors of length n of w. The following program takes as input a finite partial word over a binary alphabet and outputs all nonzero values of the subword complexity function of this word. The binary alphabet must be {a,b}, and the ^ symbol must represent a hole.

Get Java Now!

Valid XHTML 1.0 Strict Valid CSS!