Avoidable Patterns in Partial Words
F. Blanchet-Sadri, Kevin Black, and Andrew Zemke
Abstract

Background

In the process of investigating pattern avoidance in partial words, we developed numerous algorithms to assist us in our work. Among these were programs that let us determine if a pattern occurs in a word, compute the sparsity of partial word or an infinite word generated by a morphism, and show that an infinite word generated by two morphisms avoided a pattern. (For definitions of those terms, we encourage you to read our paper, as well as the papers to which it refers.) We were originally running these algorithms from a command line interface that we wrote, but we thought that a command line interface would probably not be as user friendly as a graphical user interface should we decide to make our programs available online. The result is what we call the "PWord Sandbox", shown above. It allows the user to easily perform most of the tasks of our original command line interface while simultaneously providing a means of graphical organization. Read on for more information on how to use it.

Creating Objects

To create a word, pattern, or morphism, click the appropriate button on the left side of the bottom toolbar. The first prompt will ask you for the name of the object you are about to create. Short names (one or two letters) are recommended. The second prompt is specific to the object you are creating.

  • Words
    For words, simply enter the word in the second prompt. A word must consist of alphanumeric (A-Z, a-z, 0-9) characters. We use carets ( ^ ) to represent holes in a partial word.

  • Patterns
    Patterns are similar to words, in that you enter the pattern in the second prompt. However, patterns must contain only alphabetical characters (no holes, and no numbers), and there is a distinction between uppercase and lowercase letters. An uppercase letter indicates a pattern variable, while a lowercase letter indicates a constant.

  • Morphisms
    The second prompt when entering a morphism will be for the domain of the morphism. Enter all of the letters for which the morphism should have images. Following that, you will be prompted for the image of each letter in the domain. Enter these as you would a word, using a caret for holes as necessary.

Once you have completed all of the prompts, the new object will appear in the center of the sandbox. (Note that it may be necessary to move other objects out of the way to see it (see "Moving Objects Around", below). Each object is represented by a rectangle that displays all of the information relevant to that object. The name is shown at the top of the box (which is colored to indicate what kind of object it is), and the contents of the object are shown below.

Moving Objects Around

To move an object in the sandbox, simply click and hold on the object's name (the colored region) and drag the object to the desired location. Release the mouse button to drop the object.

Deleting Objects

The trash can in the lower right corner of the sandbox can be used to delete objects. (If you cannot see the trash can, you may need to reload this page.) Drag an object and release it over the trash can to remove it from the sandbox. Note: deleting an object cannot be undone. Choose wisely!

Applying Morphisms

If you have a morphism and a word in the domain of the morphism, you can easily find the image of the word under that morphism by dragging the word over the morphism. When you release the word, it is moved to the left of the morphism, while the image is placed on the right of the morphism. The image then functions like any other word in the sandbox.

Running Algorithms

On the bottom toolbar there are four buttons to the right of those used to add object to the sandbox. These four buttons each give you the ability to run an algorithm using words, patterns, or morphisms in the sandbox. To set up an algorithm, click the button of the one you want to use. A new bar (called the "input bar") will appear at the top of the sandbox. Each algorithm has a different input bar, but they all work the same. Each one gives you boxes into which you can drag the objects that you want to use as arguments for the algorithm.

For an example, click the "Pattern Finder" button near the bottom center of the sandbox. The input box at the top of the sandbox prompts for a pattern and for a word search for the given pattern. The checkbox lets you change whether or not the algorithm searches for trivial occurrences of the pattern. Create a word "ab^a" and a pattern "AA" (name them whatever you like). To use them in the pattern finder algorithm, drag each over the input bar and release (where you release the object over the input bar is not important, so anywhere is fine). When you add each object, you will notice that the input bar will change its display to show the names of the objects that you have added. Once you have added the arguments required for the algorithm, the "Go!" button to the right of the input bar will become usable. For the first run, keep the "Allow Trivial" checkbox unchecked, and click the "Go!" button. Since the word we used does not nontrivially meet the pattern, you will get a message in the center of the screen informing you of this. (Click the "X" on the bottom of the message to dismiss it, or move it around if you want to keep it.) Next, check the "Allow Trivial" box and click "Go!" again. Since "ab^a" trivially meets the pattern "AA", you will get a message informing you that the word meets the pattern. You will also see that a morphism has been added to the view that maps the pattern variables into a factor of the word. When you are done using the algorithm, click the "Close" button on the input view.

Here if a brief explanation of the other three algorithms.

  • Check HDOL System
    Given a seed word, an outer morphism, and an inner morphism, this algorithm determines if the word obtained by iterating the inner morphism over the seed word infinitely many times and then applying the outer morphism once avoids the given pattern. We provide the option to allow trivial occurrences of the pattern.

    When setting this algorithm up, you must enter the inner morphism before the outer one. Once you enter the inner morphism, any subsequent morphisms added will be treated as the outer morphism. To change the inner morphism it is necessary to close the input bar and start over.

  • Iterate Morphism
    This algorithm takes a morphism, a seed word, and a positive integer (typed into the text field that appears in the input view), and iterates the morphism over the seed word the given number of times. The resulting word is added to the sandbox.

  • Find Sparsity
    This will compute the sparsity of either a word or of an infinite word generated by an iterated morphism over a seed word. If you do not give a morphism, the algorithm will simply find the sparsity of the word. If you do give a morphism and a seed word, the algorithm will compute the sparsity of the word generated by iterating the morphism, but only if the word is in the domain of the morphism and the morphism is iterable.

It is worth noting that some of the algorithms, particularly "Find Pattern" and "Check HDOL System" may take quite a long time to run. While both usually finish in a few seconds, on large words or complex patterns they may take several minutes or even hours. We point out that these implementations are provided only as demonstrations of the algorithms and are not intended for heavy use.



This page may not function correctly if you do not have the latest versions of the Java Runtime Environment and Java Plugin, available here. If you have any questions about our work or are interested in obtaining the command line implementation of our framework, please contact us at the email addresses provided in the paper. Thank you and enjoy!