Parameter word
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 formula_1, over a given alphabet formula_2, is a sequence of formula_1 characters, some of which may be drawn from  formula_2 and the others of which are formula_5 distinct wildcard characters formula_6. 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 formula_7, the next one that is different from formula_7 must be formula_9, 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 formula_2, of length formula_1, is A word represents a set of formula_12 strings (0-parameter words), obtained by substituting a symbol of formula_2 for each wildcard character. This set of strings is called a parameter set of combinatorial cube, and formula_5 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 formula_2 is an alphabet and formula_16 is a group with an action on formula_2, 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 formula_2 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 formula_2, of length formula_1, is Example. In the game of tic-tac-toe, the cells of the game board can be given two integer coordinates formula_21 from the alphabet formula_22. Concatenating these two coordinates produces a string representing each cell, one of the nine strings formula_23 or formula_24. There are seven one-parameter words of length two over this alphabet, the words formula_25 and formula_26. 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 formula_27 corresponds to  the combinatorial line formula_28, and the one-parameter word formula_26 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 formula_30 and formula_31 while leaving the element formula_32 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 formula_26 labeled by the identity element for its first formula_34 and the reversing non-identity element for the second formula_34; its combinatorial line is the final winning line of the tic-tac-toe board, Composition. For three given integer parameters formula_36, it is possible to combine two parameter words, formula_37 and formula_38, to produce another parameter word formula_39 . To do so, simply replace each copy of the formula_40th wildcard symbol in formula_41 by the formula_40th character in formula_43. This will necessarily produce a word of length formula_1 that uses each of the wildcard symbols in formula_43 at least once, in ascending order, so it produces a valid word of length formula_1. 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. Combinatorial enumeration. The number of parameter words in formula_47 for an alphabet of size formula_48 is an formula_48-Stirling number of the second kind formula_50. These numbers count the number of partitions of the integers in the range formula_51 into formula_52 non-empty subsets such that the first formula_48 integers belong to distinct subsets. Partitions of this type can be placed into a bijective equivalence with the parameter words, by creating a word with a character for each of the formula_1 integers  in the range formula_55, setting this character value to be either an integer in formula_56 belonging to the same subset of the partition, or a wildcard character for each subset of the partition that does not contain an integer in formula_56. The formula_48-Stirling numbers obey a simple recurrence relation by which they may easily be calculated. Applications. In Ramsey theory, parameter words and combinatorial cubes may be used to formulate the Graham–Rothschild theorem, according to which, for every finite alphabet and group action, and every combination of integer values formula_59, formula_5, and formula_48, there exists a sufficiently large  number formula_1 such that if each combinatorial cube over strings of length formula_1 is assigned one of formula_48 colors, then there exists a combinatorial cube all of whose subcubes have the same color. This result is a key foundation for structural Ramsey theory, and is used to define Graham's number, an enormous number used to estimate the value of formula_1 for a certain combination of values. In computer science, in the problem of searching for duplicate code, the source code for a given routine or module may be transformed into a parameter word by converting it into a sequence  of tokens, and for each variable or subroutine name, replacing each copy of the same name with the same wildcard character. If code is duplicated, the resulting parameter words will remain equal even if some of the variables or subroutines have been renamed. More sophisticated searching algorithms can find long duplicate code sections that form substrings of larger source code repositories, by allowing the wildcard characters to be substituted for each other. An important special case of parameter words, well-studied in the combinatorics of words, is given by the partial words. These are strings with wildcard characters that may  be substituted independently of each other, without requiring that some of the substituted characters be equal or controlled by a group action. In the language of parameter words, a partial word may be described as a parameter word in which each wildcard symbol appears exactly once. However, because there is no repetition of wildcard symbols, partial words may be written more simply by omitting the subscripts on the wildcard symbols.