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 k {\displaystyle k} -parameter word of length n {\displaystyle n} , over a given alphabet A {\displaystyle A} , is a sequence of n {\displaystyle n} characters, some of which may be drawn from A {\displaystyle A} and the others of which are k {\displaystyle k} distinct wildcard characters ∗ 1 , ∗ 2 , … , ∗ k {\displaystyle *_{1},*_{2},\ldots ,*_{k}} . 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 ∗ 1 {\displaystyle *_{1}} , the next one that is different from ∗ 1 {\displaystyle *_{1}} must be ∗ 2 {\displaystyle *_{2}} , 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 k {\displaystyle k} -parameter words over A {\displaystyle A} , of length n {\displaystyle n} , is denoted A ( n k ) {\displaystyle A{\tbinom {n}{k}}} . A k {\displaystyle k} -parameter word represents a set of | A | k {\displaystyle |A|^{k}} strings (0-parameter words), obtained by substituting a symbol of A {\displaystyle A} for each wildcard character. This set of strings is called a parameter set of combinatorial cube, and k {\displaystyle k} 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 A {\displaystyle A} is an alphabet and G {\displaystyle G} is a group with an action on A {\displaystyle A} , then a G {\displaystyle G} -labeled parameter word is a k {\displaystyle k} -parameter 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 A {\displaystyle A} 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 G {\displaystyle G} -labeled k {\displaystyle k} -parameter words over A {\displaystyle A} , of length n {\displaystyle n} , is denoted [ A , G ] ( n k ) {\displaystyle [A,G]{\tbinom {n}{k}}} .
… excerpt ends here. Continue reading the full article.
