In the mathematical study of combinatorics on words, a parameter word is a string over a given alphabet having some number of wildcard characters. The set of strings matching a given parameter word is called a parameter set or combinatorial cube. Parameter words can be composed, to produce smaller subcubes of a given combinatorial cube. They have applications in Ramsey theory and in computer science in the detection of duplicate code.
Definitions and notation
Formally, a word of length , over a given alphabet , is a sequence of characters, some of which may be drawn from and the others of which are distinct wildcard characters . Each wildcard character is required to appear at least once, but may appear multiple times, and the wildcard characters must appear in the order given by their indexes: the first wildcard character in the word must be , the next one that is different from must be , etc. As a special case, a word over the given alphabet, without any wildcard characters, is said to be a 0-parameter word. For 1-parameter words, the subscripts may be omitted, as there is no ambiguity between different wildcard characters. The set of all words over , of length , is
A word represents a set of strings (0-parameter words), obtained by substituting a symbol of for each wildcard character. This set of strings is called a parameter set of combinatorial cube, and is called its dimension. A one-dimensional combinatorial cube may be called a combinatorial line.
In a combinatorial cube, each copy of a particular wildcard character must have the same replacement. A generalization of parameter words allows different copies of the same wildcard character to be replaced by different characters from the alphabet, in a controlled way. If is an alphabet and is a group with an action on , then a parameter word is a word together with an assignment of a group element to each wildcard character in the word. The first occurrence of each wildcard character must be assigned the identity element of the group. Then, the strings represented by a labeled parameter word are obtained by choosing a character of for each wildcard character, and substituting the result of combining that character with the group element labeling each copy of that character. The set of all words over , of length , is
Example
In the game of tic-tac-toe, the cells of the game board can be given two integer coordinates from the alphabet . Concatenating these two coordinates produces a string representing each cell, one of the nine strings or . There are seven one-parameter words of length two over this alphabet, the words and . The corresponding combinatorial lines form seven of the eight lines of three cells in a row of the tic-tac-toe board; for instance, the one-parameter word corresponds to the combinatorial line , and the one-parameter word corresponds to the combinatorial
However, one of the eight winning lines of the tic-tac-toe game is missing from this set of combinatorial lines: the antidiagonal It is possible to obtain this line as a combinatorial line (without including any other combinations of cells that would be invalid for tic-tac-toe) by using a group with two elements, and an action in which the non-identity element swaps the alphabet letters and while leaving the element in place. There are eight labeled one-parameter words of length two for this action, seven of which are obtained from the unlabeled one-parameter words by using the identity label for all wildcards. These seven have the same combinatorial lines as before. The eighth labeled word consists of the word labeled by the identity element for its first and the reversing non-identity element for the second ; its combinatorial line is the final winning line of the tic-tac-toe board,
Composition
For three given integer parameters , it is possible to combine two parameter words, and , to produce another parameter word . To do so, simply replace each copy of the th wildcard symbol in by the th character in . This will necessarily produce a word of length that uses each of the wildcard symbols in at least once, in ascending order, so it produces a valid word of length . This notion of composition can also be extended to composition of labeled parameter words (both using the same alphabet and group action), by applying the group action to the non-wildcard substituted characters and composing the group labels for the wildcard substituted characters. A subset of a combinatorial cube is a smaller combinatorial cube if it can be obtained by a composition in this way.