Gray Codes for A-Free Strings

Matthew B. Squire^{∗} IBM Corporation Dept NFVA/Bldg 664 P.O. Box 12195 Research Triangle Park, NC 27709

              Email: msquire@vnet.ibm.com

Submitted: July 10, 1995; Accepted February 14, 1996.

Abstract

For any q ≥ 2, let Σ_{q} = {0, …, q−1}, and fix a string A over Σ_{q}. The A-free strings of length n are the strings in Σ_{q}^{n} which do not contain A as a contiguous substring. In this paper, we investigate the possibility of listing the A-free strings of length n so that successive strings differ in only one position, and by ±1 in that position. Such a listing is a Gray code for the A-free strings of length n.

We identify those q and A such that, for infinitely many n ≥ 0, a Gray code for the A-free strings of length n is prohibited by a parity problem. Our parity argument uses techniques similar to those of Guibas and Odlyzko (Journal of Combinatorial Theory A 30 (1981) pp. 183–208) who enumerated the A-free strings of length n. When q is even, we also give the complementary positive result: for those A for which an infinite number of parity problems do not exist, we construct a Gray code for the A-free strings of length n for all n ≥ 0. Mathematical Review Subject Numbers: 68R15, 05A15.

1 Introduction

Fix q ≥ 2 and let Σ_{q} = {0, …, q−1}. When we refer to strings, we mean strings over Σ_{q}. For any strings A and B, an A-factor of B is a contiguous substring of B equal to A. Fix a string A, and let F(n) = F(n; A) be the strings of length n which do not have an A-factor. The set F(n) consists of the A-free strings of length n.

the electronic journal of combinatorics 3 (1996) #R17 2

We are interested in Gray codes for F(n). A Gray code for a set is a listing of its elements so that successive elements are “similar.” Define two strings in Σ_{q}^{n} to be similar if they differ in exactly one position, and by ±1 in that position. When q is even, the addition is done modulo q, but the addition is not modular for odd q.

∗Research supported by National Science Foundation Grant No. DMS9302505.

Given S ⊆ Σ_{q}^{n}, we can form a graph whose vertices are the strings in S, and which has edges between all pairs of similar strings. Let G_{q}(S) denote this graph. Then G_{q}(S) is a bipartite subgraph of the q-ary n-cube. A Gray code for S is equivalent to a Hamilton path of G_{q}(S). For a bipartite graph with bipartition (X, Y) to have a Hamilton path, X and Y must have cardinalities which differ by at most one. Call a string B = b_{0} … b_{n−1} even if ∑ b_{i} is even, and odd if ∑ b_{i} is odd. If S^{+} and S^{−} denote the even and odd strings in S, respectively, then (S^{+}, S^{−}) is a bipartition of G_{q}(S). Thus, a Gray code for F(n) is only possible if the numbers of even and odd A-free strings differ by at most one.

In this paper, we investigate the existence of Gray codes for A-free strings. More specifically, we characterize the q and A for which a Gray code for F(n) cannot exist for infinitely many n due to problems with the cardinalities of the even and odd strings. When the number of even and odd strings in F(n) differ by more than one, we say that F(n) has a parity problem. We say that F(n) has infinite parity problems to indicate that F(n) has a parity problem for infinitely many n.

The set F(n) can be defined more generally. Let A be any finite set of strings. The A-free strings of length n, F(n; A), are the strings of length n which do not contain any A ∈ A as a substring. The previously mentioned definition of F(n) restricted A to be a singleton set. Let f(n) = |F(n; A)|, and let

F(z) = ∑_{n≥0} f(n)z^{−n}

be its generating function. Many authors [7, 6, 12, 3, 8, 10] have shown F(z) to be a rational generating function of the form

F(z) = \frac{P (z)}{Q(z)},

where P (z) and Q(z) are polynomials in z. Guibas and Odlyzko [6] provide efficient means of determining the polynomials P (z) and Q(z) for arbitrary A.

When A is a singleton set, Guibas and Odlyzko [6] present a beautiful and concise formula for F(z) which depends only upon how the string A “overlaps” itself. The authors use the correlation of a string to measure self-overlaps. Gardner [1] attributes the notion of correlation to Conway. Let A = a_{0} … a_{m−1} and B = b_{0} … b_{n−1}. The correlation of A over B, denoted AB, is the binary string of length m where bit i, 0 ≤ i < m, is defined as follows. Place B under A with b_{0} under a_{i}. If the overlapping parts of the string match, then bit i of AB is one, otherwise it is zero. Refer to Figure 1 for an example. The autocorrelation of A is AA.

It is often helpful to view AB as the coefficient sequence of a polynomial. If AB = c_{0} … c_{m−1}, let AB_{z} = ∑_{i=0}^{m−1} c_{i}z^{m−1−i}. See Figure 1 for an example. Guibas and Odlyzko [6] show that when A = {A},

F(z) = \frac{zAA_{z}}{(z − q)AA_{z} + 1}.  (1)

AB_{z}^{∗} =  z^{3} -z AB^{∗} = 0 0 0 1 0 -1 0 AB^{−} = 0 0 0 0 0 1 0 AB^{+} = 0 0 0 1 0 0 0 AB_{z} =  z^{3} +z AB = 0 0 0 1 0 1 0 A = 1001010  B = 101011

Figure 1: Correlations and correlation polynomials

We are more concerned with determining the parity difference for F(n) rather than the cardinality of F(n). The parity difference of F(n) is the difference between the number of even and odd strings in F(n). When the parity difference is greater than one, no Gray code for F(n) can exist. To this end, we define the positive correlation of A over B, denoted AB^{+}, in an analogous manner to the correlation of A over B. For bit i of AB^{+} to be one, bit i of AB must be one and a_{i} … a_{m−1} must be even. The negative correlation of A over B, AB^{−}, is defined similarly except that a_{i} … a_{m−1} must be odd. Define the parity correlation of A over B, AB^{∗}, to be the string in {0, ±1}^{m} equal to AB^{+} − AB^{−}, where the subtraction is performed bitwise. Refer to Figure 1 for an example. The parity correlation determines the parity difference for F(n) in much the same way as the correlation determines the cardinality of F(n). Let AB_{z}^{∗} (AB_{z}^{+}, AB_{z}^{−}) denote the polynomial in z whose coefficient sequence is given by AB^{∗} (AB^{+}, AB^{−}).

In Section 2, we develop recursive definitions and generating functions for the parity difference of F(n). In Section 3, the generating functions are used to characterize those q and A for which F(n) has infinite parity problems. For these q and A, we know that Gray codes for F(n) often cannot exist. For even q and for those A which do not have infinite parity problems, Gray codes for F(n) are constructed for all n. This is done in Section 4. When q is odd and F(n) has no parity problems, we leave it open to discover Gray codes for F(n). In Section 5, we summarize the results of the paper and indicate several related questions. Throughout this paper, A = a_{0} … a_{m−1} represents the chosen string for F(n) = F(n; A), and m denotes the length of A. We assume m > 0 because every string contains an ϵ-factor, where ϵ denotes the null string.

2 Generating Functions and Recurrences

As mentioned in Section 1, the generating function F(z) has been well studied. In this section, a similar argument is used to obtain the generating function for the parity difference of F(n).

Let F^{+}(n) and F^{−}(n) denote the even and odd strings of F(n), and let f^{+}(n) and f^{−}(n) denote the cardinalities of these sets. Denote the parity difference of F(n) by f^{∗}(n) = f^{+}(n) − f^{−}(n). We wish to determine the generating function

F^{∗}(z) = ∑_{n≥0} f^{∗}(n)z^{−n}.

To do so, we develop two identities for F^{∗}(z). The two identities are then combined to solve for F^{∗}(z). Our approach follows that of Guibas and Odlyzko [6].

Before developing the first identity, we introduce several more concepts. For i ∈ Σ_{q}, let F_{i}(n) denote the strings in F(n) which end with i. Also, let G_{A}(n) be the strings of length n which contain exactly one A-factor, and the A-factor is a suffix of the string. Our notation for cardinalities and even and odd strings is extended to the sets F_{i}(n) and G_{A}(n). So, for example, F_{i}^{+}(n) are the even strings in F_{i}(n), and g_{A}^{∗}(n) is the parity difference of G_{A}(n). Let G_{A}^{∗}(z) = ∑_{n≥0} g_{A}^{∗}(n)z^{−n} be the generating function for g_{A}^{∗}(n). For any strings X and Y, X ∗ Y denotes the concatenation of X and Y.

We now develop the first identity for F^{∗}(z). Assume that a_{m−1} is even, and suppose we are given n ≥ 0 and B ∈ F^{+}(n). Then C = B ∗ a_{m−1} is also an even string, and C either ends with A or it does not. Since this is true for all B ∈ F^{+}(n), f^{+}(n) = g_{A}^{+}(n+1)+f_{a_{m−1}}^{+}(n+1). Every string in F(n+1) must terminate with some character, so F^{+}(n + 1) = ∪_{i=0}^{q−1}F_{i}^{+}(n + 1). Let S = Σ_{q} \{a_{m−1}}, and let S^{+} and S^{−} denote the subsets of S consisting of the even and odd characters, respectively. For all i ∈ S, B ∈ F(n) if and only if B ∗ i ∈ F_{i}(n + 1). Therefore,

f^{+}(n) = g_{A}^{+}(n + 1) + f_{a_{m−1}}^{+}(n + 1)
= g_{A}^{+}(n + 1) + f^{+}(n + 1) − ∑_{i∈S} f_{i}^{+}(n + 1)
= g_{A}^{+}(n + 1) + f^{+}(n + 1) − ∑_{i∈S^{+}} f^{+}(n) − ∑_{i∈S^{−}} f^{−}(n)
= g_{A}^{+}(n + 1) + f^{+}(n + 1) − |S^{+}|f^{+}(n) − |S^{−}|f^{−}(n).  (2)

We similarly arrive at

f^{−}(n) = g_{A}^{−}(n + 1) + f^{−}(n + 1) − |S^{+}|f^{−}(n) − |S^{−}|f^{+}(n).  (3)

Subtracting eq. (3) from eq. (2) yields

(|S^{+}| − |S^{−}| + 1)f^{∗}(n) = g_{A}^{∗}(n + 1) + f^{∗}(n + 1).  (4)

If A terminates with an odd character, the corresponding equation is

(|S^{+}| − |S^{−}| − 1)f^{∗}(n) = g_{A}^{∗}(n + 1) + f^{∗}(n + 1).  (5)

We now show that eqs. (4) and (5) depend only on the parity of q, not on the actual value of q or on a_{m−1}. Suppose q = 2k and a_{m−1} is even. Then |S^{+}| = k − 1, |S^{−}| = k, and the coefficient of f^{∗}(n) in eq. (4) collapses to zero. If q = 2k and a_{m−1} is odd, then the coefficient of f^{∗}(n) in eq. (5) is again zero. When q is even, f^{∗}(n) = −g_{A}^{∗}(n) for n > 0. By multiplying both sides by z^{−n}, summing over n ≥ 0, and using f^{∗}(0) = 1 and g_{A}^{∗}(0) = 0, we arrive at

F^{∗}(z) = −G_{A}^{∗}(z) + 1  when q is even.  (6)

B  A A D 0  t − 1 0  n−1  n+m−1 ^{r}

Figure 2: Overlaps for the second identity

When q is odd, the coefficient of f^{∗}(n) in both eqs. (4) and (5) collapses to one. For odd q, f^{∗}(n) = g_{A}^{∗}(n + 1) + f^{∗}(n + 1) for all n ≥ 0. Following the same procedure as before, we get

(z − 1)F^{∗}(z) = −zG_{A}^{∗}(z) + z  when q is odd.  (7)

Equations (6) and (7) constitute the first identity for F^{∗}(z).

We now develop the second relationship between F^{∗}(z) and G_{A}^{∗}(z). Fix n ≥ 0 and let B ∈ F(n). Then B ∗A = C = c_{0} … c_{n+m−1} certainly contains an A-factor. Let t be such that c_{t−m} … c_{t−1} is the leftmost A-factor in C. Refer to Figure 2 for an illustration. Then t > n because B does not have an A-factor, and D = c_{0} … c_{t−1} ∈ G_{A}(t). Let r = t − n ≥ 1. Then c_{t−r} … c_{t−1} = a_{0} … a_{r−1} because these characters begin the A in B ∗ A. However, c_{t−r} … c_{t−1} = a_{m−r} … a_{m−1} because D ends in A. Therefore, a_{m−r} … a_{m−1} = a_{0} … a_{r−1}, and bit (m − r) of AA is one. For 1 ≤ i ≤ m, let i ∈ AA denote that bit (m − i) of AA is 1 (similarly for AA^{+} and AA^{−}). If a_{m−r} … a_{m−1} has even parity (r ∈ AA^{+}), then the parity of D is equal to the parity of B. If a_{m−r} … a_{m−1} has odd parity (r ∈ AA^{−}), then the parities of B and D are different. In this way, each B ∈ F^{+}(n) maps to exactly one D in (∪_{r∈AA^{+}}G_{A}^{+}(n + r)) ∪ (∪_{r∈AA^{−}}G_{A}^{−}(n + r)). Conversely, given a D in (∪_{r∈AA^{+}}G_{A}^{+}(n + r)) ∪ (∪_{r∈AA^{−}}G_{A}^{−}(n + r)), removing the last r characters gives a unique B in F^{+}(n). Therefore,

f^{+}(n) = ∑_{r∈AA^{+}} g_{A}^{+}(n + r) + ∑_{r∈AA^{−}} g_{A}^{−}(n + r)
f^{−}(n) = ∑_{r∈AA^{+}} g_{A}^{−}(n + r) + ∑_{r∈AA^{−}} g_{A}^{+}(n + r)

Subtracting the latter equation from the former yields

f^{∗}(n) = ∑_{r∈AA^{+}} g_{A}^{∗}(n + r) − ∑_{r∈AA^{−}} g_{A}^{∗}(n + r).

Observe that g_{A}(n) = 0 for n < m because m characters are required for an A-factor. Isolating on the first summation above, we see that

∑_{n≥0} ∑_{r∈AA^{+}} g_{A}^{∗}(n + r)z^{−n} = ∑_{r∈AA^{+}} z^{r} ∑_{n≥0} g_{A}^{∗}(n + r)z^{−(n+r)} = ∑_{r∈AA^{+}} z^{r}G_{A}^{∗}(z).

The last term is just zAA_{z}^{+}G_{A}^{∗}(z), so

F^{∗}(z) = zAA_{z}^{+}G_{A}^{∗}(z) − zAA_{z}^{−}G_{A}^{∗}(z) = zAA_{z}^{∗}G_{A}^{∗}(z).  (8)

Eq. (8) can be combined with eqs. (6) and (7) to obtain

F^{∗}(z) = \frac{zAA_{z}^{∗}}{zAA_{z}^{∗} + 1}  when q is even,  (9)
F^{∗}(z) = \frac{zAA_{z}}{(z − 1)AA_{z}^{∗} + 1}  when q is odd.  (10)

Since F^{∗}(z) is rational with a degree m polynomial in the denominator, f^{∗}(n) satisfies a degree m recurrence [8]. This recurrence can be used to efficiently calculate f^{∗}(n). In the following section, F^{∗}(z) is used to identify those q and A for which the set F(n) has infinite parity problems. Constructive results are presented in Section 4.

3 Parity problems

In this section, we examine the generating function F^{∗}(z) and determine for which q and which A a Gray code for F(n) is not always possible. For each q, we characterize all A for which F(n) has infinite parity problems.

Let H(z) = ∑ a_{n}z^{−n}. It is well known that the rate of growth of the a_{n} is highly dependent upon the modulus of the greatest singularity of H(z) (see, for example, Wilf [11]).

Theorem 3.1 Let H(z) = ∑_{n≥0} a_{n}z^{−n} be analytic on the disk |z| > R, let a singularity of H(z) of largest modulus be at a point α_{0}, and let ϵ > 0 be given. For infinitely many n we have

|a_{n}| > (|α_{0}| − ϵ)^{n} .

In particular, if H(z) has a singularity of modulus strictly greater than one, then the coefficients of H(z) are unbounded in absolute value.

The singularities of F^{∗}(z) are the roots of the polynomial in the denominator of F^{∗}(z). This polynomial is either zAA_{z}^{∗} + 1 (when q is even) or (z − 1)AA_{z}^{∗} + 1 (when q is odd). If the polynomial in question has a root of modulus greater than one, then Theorem 3.1 implies F(n) has infinite parity problems.

Let p(z) be a polynomial with integer coefficients and a unit leading coefficient. Suppose that all of the roots of p(z) are contained in the closed unit disk of the complex plane. This implies (see [9, Problem 200, page 145]) that the non-zero roots of p(z) are roots of unity. The n^{th} cyclotomic polynomial, ϕ_{n}(z), can be defined as ϕ_{n}(z) = ∏(z − θ), where the product is taken over all primitive n^{th} roots of unity. Therefore, p(z) can be expressed as a monomial z^{k} times a product of cyclotomic polynomials. A polynomial q(z) is self-reciprocal if α being a non-zero root of q(z) implies 1/α is also a root. Cyclotomic polynomials are self-reciprocal, as are products of self-reciprocal polynomials. Thus, if p(z) has all roots in the closed unit disk, then p(z) is self-reciprocal. It can be easily checked that if q(z) = ∑_{i=0}^{m} q_{i}z^{m−i} is selfreciprocal then (q_{0}, …, q_{m}) = ±(q_{m}, …, q_{0}).

Let (p_{0}, …, p_{m}) be the coeffients of the polynomial in the denominator of F^{∗}(z). To prove that F(n) has infinite parity problems, we need only show that (p_{0}, …, p_{m}) ≠ ±(p_{m}, …, p_{0}). This is the approach taken in Sections 3.1 and 3.2.

3.1 Parity problems when q is even

Throughout Section 3.1, q is assumed even. The polynomial in the denominator of F^{∗}(z) is then p(z) = p(z; A) = zAA_{z}^{∗} + 1. This polynomial either has a root outside the closed unit disk, or it is self-reciprocal. Given any string A, one can determine whether p(z) is self-reciprocal by simply examining its coefficients.

We wish to characterize those A for which the roots of p(z) all lie in the closed unit disk, with the characterization based directly on A and not p(z). A period of A is an integer p such that a_{i} = a_{i+p} for all 0 ≤ i < m − p. The periods of A are the positions of the ones in AA. With each non-zero period p, there is a corresponding prefix a_{0} … a_{p−1} of A. Call B a base of A if B = a_{0} … a_{p−1} for some period p > 0 of A. For any base B of A, A = B ∗ ⋯ ∗ B ∗ C, where C is a (possibly empty) prefix of B. The minimal period of A is the smallest non-zero period of A. If A has no non-zero period, then its minimal period is defined to be m. The minimal base of A is the base corresponding to the minimal period.

Let p be the minimal period of A and let B be its minimal base. The string A is periodic if p < m and p divides m. In this case, A = B ∗ ⋯ ∗ B. Note that the minimal base of any string cannot itself be periodic. If A is not periodic, then it is aperiodic.

Not every binary string is an autocorrelation. For example, 000 is not the autocorrelation of any string. Binary strings which are autocorrelations are known to satisfy many properties, including the Forward Propagation Rule [5]:

Definition 3.1 A length m bit vector satisfies the Forward Propagation Rule if bits i and i + k being one (k ≥ 0) implies bit i + jk is one for all i ≤ i + jk < m.

A corollary of the Forward Propagation Rule is that if A = B ∗ ⋯ ∗ B ∗ C, where B is the minimal base of A and C is a non-empty (and possibly non-proper) prefix of B, then AA = 10^{p−1} ∗ ⋯ ∗ 10^{p−1} ∗ CC. The string 10 ⋯ 0 is the trivial autocorrelation, and if AA = 10 ⋯ 0, then A is trivially autocorrelated, or t.a.

Suppose that p(z) = zAA_{z}^{∗} + 1 has all of its roots in the closed unit disk, so p(z) is self-reciprocal. If X = AA ∗ 1, then it must be that X = X^{R}, where X^{R} denotes the reverse of X. We claim that this can only occur if A is t.a., or if A is periodic with a t.a. minimal base. It is simple to verify that in either of these cases, X = X^{R} and the roots of p(z) are roots of unity.

Now suppose that A is not t.a., and that A is not periodic with a t.a. minimal base. For instance, suppose that A is periodic, but that its minimal base B is not t.a. Then bit p − j of BB is one for some 0 < j < p. In this case, bit m − j of AA is also one, but bits 1 through p − 1 of AA are zero. This implies X ≠ X^{R}, where X = AA ∗ 1. Thus, p(z) cannot be self-reciprocal, so it must have a root outside the closed unit disk. The case when A is aperiodic but not t.a. can be handled similarly. Therefore, p(z) has all roots in the closed unit disk iff A is t.a., or if A is periodic with a t.a. minimal base. For all other A, F(n) has infinite parity problems.

We could prove directly that if A is t.a. or A is periodic with a t.a. minimal base, then |f^{∗}(n)| ≤ 1 for all n. In this case, the roots of p(z) are all roots of unity, so f^{∗}(n) is a periodic function, ie f^{∗}(n) = f^{∗}(n+r) for some r > 0. By showing that |f^{∗}(n)| ≤ 1 for 0 ≤ n < r, we could conclude that |f^{∗}(n)| ≤ 1 for all n. In Section 4, we actually construct Gray codes for F(n) for all n and any such A. This implies F(n) never has a parity problem. We therefore omit this latter part of the proof and simply state:

Theorem 3.2 Fix an even q ≥ 2, m > 0, and A ∈ Σ_{q}^{m}. If A is t.a. or A is periodic with a t.a. minimal base, then F(n) has no parity problems. Otherwise, F(n) has infinite parity problems.

It may seem to the reader that t.a. strings are rare. In fact, they are not. Guibas and Odlyzko [5, 4] have studied the number of strings with a given autocorrelation. When q = 2, about 27% of all strings [5] are t.a. For q ≥ 3, the majority of strings are t.a., and as q gets larger, the vast majority of strings are t.a. For large q, the fraction of t.a. strings is about (q − 2)/(q − 1).

In Theorem 3.2, we have characterized those A for which F(n) has infinite parity problems when q is even. The odd q case is examined in the next section.

3.2 Parity problems when q is odd

When q is odd, the polynomial in the denominator of F^{∗}(z) is p(z) = p(z; A) = (z − 1)AA_{z}^{∗} + 1. If p(z) is not self-reciprocal, then F(n) has infinite parity problems.

We first show that, for certain polynomials c(z), if (z − 1)c(z) + 1 is self-reciprocal, then c(z) has two unit coefficients followed by a zero coefficient. If we interpret c(z) as AA_{z}^{∗}, then for certain strings A, if p(z) is self-reciprocal, then AA contains the substring 110.

Lemma 3.1 Let c(z) = ∑_{i=0}^{m−1} c_{i}z^{m−1−i} satisfy c_{0} ≠ 0 and c_{1} = c_{2} = c_{m−1} = 0. If (z − 1)c(z) + 1 is self-reciprocal, then c_{m−2} = c_{m−3} = 1.

Proof. Let p(z) = ∑_{i=0}^{m} p_{i}z^{m−i} = (z − 1)c(z) + 1 be self-reciprocal. Then p_{0} = c_{0}, p_{m} = 1 − c_{m−1} = 1, and for i, 0 < i < m, p_{i} = c_{i} − c_{i−1}. If p_{i} = p_{m−i} for 0 ≤ i ≤ m, then

c_{0} = p_{0} = p_{m} = 1
−c_{0} = c_{1} − c_{0} = p_{1} = p_{m−1} = c_{m−1} − c_{m−2} = −c_{m−2}
0 = c_{2} − c_{1} = p_{2} = p_{m−2} = c_{m−2} − c_{m−3}

Therefore, c_{m−2} = c_{m−3} = 1. The same result follows when p_{i} = −p_{m−i} for all i. □

Suppose c(z) = AA_{z}^{∗} in Lemma 3.1. If the conditions are satisfied and p(z) is selfreciprocal, then last three positions of AA^{∗} are 110. Applying the Forward Propagation Rule, it is easy to see that no autocorrelation can contain the substring 110. Thus, if AA is of the form 100X0 for some binary string X, then p(z) cannot be self-reciprocal.

We now examine other possible forms of AA and determine when p(z) is selfreciprocal. If AA = X1 and a_{m−1} is odd, then p(z) has constant term two, and is thus not self-reciprocal. Let p be the minimal period of A and let B be its minimal base. The rest of the analysis is divided into three cases.

Case 1: When p > 2. In this case, AA = 100X. We have already discussed the possibility that AA = 100Y 0, and the possibility that AA = 100Y 1 with a_{m−1} odd. We are left to consider when AA = 100Y 1 and a_{m−1} is even. Suppose a_{m−1} is even and AA ends in 01^{k}, k > 0. Since a_{0} = a_{m−k} = ⋯ = a_{m−1} is even, AA_{z}^{∗} = z^{k}c(z)+z^{k−1}+…+1, where c(z) is the degree (m−k−1) polynomial whose coefficients are given by the first m − k positions of AA^{∗}. The constant term of c(z) is zero. In this case,

p(z) = (z − 1)AA_{z}^{∗} + 1 = z^{k}((z − 1)c(z) + 1).

If p′(z) = (z − 1)c(z) + 1 is self-reciprocal, then the lower three coefficients of c(z) are 1, 1, 0 by Lemma 3.1. This implies bits (m−k−3) through (m−k−1) of AA are 110, again leading to a contradiction. Thus p′(z), and p(z), are not self-reciprocal.

Case 2: When p = 2. We separately examine when m is even and m is odd. First suppose m is even. Then AA = (10)^{m/2} and A = B ∗ ⋯ ∗ B for an aperiodic string B of length two. Say B is an even string, so p(z) = z^{m} − z^{m−1} + z^{m−2} ⋯ − z + 1. In this particular subcase, the roots of p(z) are roots of unity (p(z) divides z^{m+1} + 1). If B is an odd string and m = 2, then p(z) = −z^{2} + z + 1. Here, the parity differences are the Fibonacci numbers (doesn’t the generating function look familiar?). Finally, consider when B is odd and m ≥ 4. The smallest term of AA_{z}^{∗} is −z, so p(z) = ±z^{m} ∓ z^{m−1} ⋯ + z + 1, where the signs of z^{m} and z^{m−1} are different, but the signs of z and 1 are both positive. This p(z) is not self-reciprocal. Thus, when p = 2 and m is even, F(n) has infinite parity problems if the minimal base is an odd string. Otherwise, the roots of p(z) are roots of unity.

If m is odd, a similar analysis yields that F(n) has infinite parity problems if the minimal base does not consist of two even characters. If B does consist of two even characters, then the roots of p(z) all lie in the closed unit disk.

Case 3: When p = 1. We have already considered the possibility that AA = X1 and a_{m−1} is odd. We therefore need only consider when a_{m−1} is even. In this case, p(z) = z^{m}, and F^{∗}(z) is a simple polynomial with coefficients in {0, ±1}. When p = 1 and a_{0} = a_{m−1} is odd, F(n) has infinite parity problems. When a_{0} is even, F(n) does not have a parity problem for any n.

As mentioned in Section 3.2, if p(z) has all roots in the closed unit disk, then f^{∗}(n) is a periodic function. By showing that |f^{∗}(n)| ≤ 1 for 0 ≤ n < r, where r is the period of the function, we could prove that when the roots of p(z) are all in the closed unit disk, F(n) has no parity problems. As in Section 3.1, we omit this part of the proof, and state the following theorem.

Theorem 3.3 Fix an odd q ≥ 3, m > 0, and A ∈ Σ_{q}^{m} with minimal period p. If

• p > 3, or

• p = 2, m is even, and a_{0}a_{1} is odd, or

• p = 2, m is odd, and either a_{0} or a_{1} is odd, or

• p = 1 and a_{0} is odd, then F(n) has infinite parity problems. Otherwise, F(n) has no parity problems.

In Section 3, we have examined the generating function F^{∗}(z) and identified the q and A for which the coefficients of F^{∗}(z) are unbounded. In Section 4, Gray codes are constructed for F(n) when q is even and A is t.a. or A is periodic with a t.a. minimal base. These are the only A for which F(n) has no parity problems when q is even. For odd q, it remains open to find Gray codes for F(n) when F(n) has no parity problems.

4 Gray Codes for A-Free Strings when q is even

Throughout Section 4, q is assumed even. The goal of this section is to construct Gray codes for F(n) for all n ≥ 0 when A is t.a. or A is periodic with a t.a. minimal base. For all other A, Theorem 3.2 showed that F(n) has infinite parity problems. We begin by presenting the recursive identity on which our constructions are based.

Let C be a string over Σ_{q}. Define H(n; C) to be the D ∈ Σ_{q}^{n} such that C ∗ D has no A-factor. It is clear that for any k ≤ n,

H(n; C) = ⋃_{D∈H(n−k;C)} D ∗ H(k; C ∗ D).  (11)

For certain A, we construct Gray codes for H(n; C) for all n and C. Letting ϵ denote the empty string, F(n) = H(n; ϵ). Thus, for certain A, we get Gray codes for F(n).

Our method of constructing Gray codes is recursive. In Section 4.1, we describe the construction methods and present the main recursive step. Sections 4.2 through 4.5 supply the construction of the basis. The basis construction is also recursive.

4.1 Construction Overview

In this section, we overview our construction methodology. The main inductive step is given in the following lemma. Let h^{∗}(n; C) be the parity difference of H(n; C). Bold letters (L) represent sequences of strings. If L is a list of strings, then L^{R} denotes the reverse of L.

Lemma 4.1 Fix an even q ≥ 2, m > 0, and A ∈ Σ_{q}^{m}. Suppose there exists k > 0 such that both of the following conditions are true.

1. For any n, 1 ≤ n ≤ k, and for any C with no A-factor, there is a Gray code for H(n; C). When h^{∗}(n; C) = 0, there is a cyclic Gray code.

2. There exist strings S, T ∈ Σ_{q}^{k}, of equal parity, such that for any D with no Afactor, there is a Gray code for H(k; D) from S to T.

Then, for all n ≥ 1 and for all C with no A-factor, there is a Gray code for H(n; C). When h^{∗}(n; C) = 0, there is a cyclic Gray code.

Proof. We argue by induction on n. Let C be any string with no A-factor. When 1 ≤ n ≤ k, condition (1) of the lemma provides Gray codes for H(n; C). Assume n > k and recall the recursive definition of eq. (11).

By induction, there exists a Gray code L′ = D_{0}, …, D_{N−1} for H(n − k; C). For 0 ≤ i < N, let L_{i} be the Gray code for H(k; C ∗ D_{i}) from S to T which exists by condition (2). A Gray code for H(n; C) is given by

L = D_{0} ∗ L_{0}, D_{1} ∗ L_{1}^{R}, D_{2} ∗ L_{2}, …

Since S and T have equal parity, |h^{∗}(k; D)| = 1 for all D. Therefore, h^{∗}(n; C) = 0 iff h^{∗}(n − k; C) = 0, and L is cyclic iff L′ is cyclic. □

We are left with the difficult task of proving that the conditions of the lemma can be satisfied when A is t.a. and when A is periodic with a t.a. minimal base. Sections 4.2 through 4.5 show this to be true. If A is t.a., then the conditions are satisfied when k = m. If A is periodic with a t.a. minimal base, then the conditions are satisfied when k = m + p, where p is the minimal period of A.

We construct cyclic Gray codes for H(n; C) whenever h^{∗}(n; C) = 0. It is therefore important to know when h^{∗}(n; C) = 0 and when |h^{∗}(n; C)| = 1. For n ≤ m, Lemma 4.2 characterizes these two cases based upon whether H(n; C) contains certain strings. For i < j, a_{j} … a_{i} is defined to be the empty string. Every C ∈ Σ_{q}^{∗} has an ϵ-suffix.

Lemma 4.2 Fix an even q ≥ 2, m > 0 and A ∈ Σ_{q}^{m}. For any n, 1 ≤ n ≤ m, and for any C ∈ Σ_{q}^{∗}, |h^{∗}(n; C)| = 1 if and only if a_{m−n} … a_{m−2}x ∈ H(n; C) for all x ≠ a_{m−1} and C ends with a_{0} … a_{m−n−1}. Otherwise, h^{∗}(n; C) = 0.

Proof. We attempt to pair the even and odd strings in H(n; C). If every string in H(n; C) except one can be paired with a string of opposite parity, then |h^{∗}(n; C)| = 1. Arbitrarily pair the even and odd characters in Σ_{q}. For x ∈ Σ_{q}, the mate of x is the element with which x is paired. For D = d_{0} … d_{n−1} ∈ H(n; C), let D′ = d_{0} … d_{n−2}y, where y is the mate of d_{n−1}. Then (D, D′) is a perfect pairing of H(n; C) unless there exists a D ∈ H(n; C) with C ∗ D′ having an A-suffix. In this case, C ends with a_{0} … a_{m−n−1} and D = a_{m−n} … a_{m−2}z, where z is the mate of a_{m−1}. Since C ∗ D does not have an A-factor, C ∗ a_{m−n} … a_{m−2}x does not have an A-factor for any x ≠ a_{m−1}, and D is the only unpaired string in H(n; C). □

Let q, m, and A be as in the lemma. Suppose that n, 1 < n ≤ m, and C ∈ Σ_{q}^{∗} are such that |h^{∗}(n; C)| = 1. By the preceding lemma, C ∗ a_{m−n} … a_{m−1} has an A-suffix, but C ∗ a_{m−n} … a_{m−2}x does not have an A-factor for x ≠ a_{m−1}. Then (C ∗ a_{m−n}) ∗ a_{m−n+1} … a_{m−1} also has an A-suffix, and (C ∗ a_{m−n}) ∗ a_{m−n+1} … a_{m−2}x does not have an A-factor for x ≠ a_{m−1}. Thus |h^{∗}(n−1; C ∗a_{m−n})| = 1. For x ≠ a_{m−n}, since C ∗ x does not end with a_{m−n}, h^{∗}(n − 1; C ∗ x) = 0.

Now suppose n and C are such that h^{∗}(n; C) = 0. Then either a_{m−n} … a_{m−2}x ∈ H(n; C) for all x ∈ Σ_{q}, or a_{m−n} … a_{m−2}x ∉ H(n; C) for all x ∈ Σ_{q}. So h^{∗}(n − 1; C ∗ a_{m−n}) = 0. For x ≠ a_{m−n}, C ∗ x does not end with a_{m−n}, so h^{∗}(n − 1; C ∗ x) = 0.

We thus get the following corollary of Lemma 4.2.

Corollary 4.1 Fix an even q ≥ 2, m > 0, and A ∈ Σ_{q}^{m}. For any n, 1 < n ≤ m, and any C ∈ Σ_{q}^{∗}, h^{∗}(n; C) = 0 if and only if h^{∗}(n − 1; C ∗ x) = 0 for all x ∈ Σ_{q}. Also, |h^{∗}(n; C)| = 1 if and only if |h^{∗}(n − 1; C ∗ a_{m−n})| = 1 and h^{∗}(n − 1; C ∗ x) = 0 for all x ∈ Σ_{q}\{a_{m−n}}.

When q = 2 and n ≤ m, Gray codes for H(n; C) are studied in Section 4.2. When q ≥ 4 is even and n ≤ m, Gray codes are examined in Section 4.3. Gray codes when n ≤ m do not require A to be t.a. or to be periodic with a t.a. minimal base. By Lemma 4.2, F(n) cannot have a parity problem when n ≤ m. Only as n gets larger can parity problems arise. Gray codes for arbitrary n are discussed in Sections 4.4 and 4.5. The former section considers when A is t.a., while the latter section considers when A is periodic with a t.a. minimal base.

4.2 Gray codes when q = 2 and n ≤ m

In this section we construct Gray codes for H(n; C) when q = 2 and n ≤ m. Throughout Section 4.2, it is assumed that q = 2. The constructions of this section also assume that A ends with two identical characters. In Sections 4.4 and 4.5, we show how to remove this restriction. For x ∈ Σ_{q}, let \overline{x} = x + 1 mod q.

The Gray code constructions of this section are based on eq. (11) when k = n − 1. For any C, define r(C) = r(C; A) to be the minimum length of any non-empty string D such that C ∗ D ends in A-factor. Such a D must be of the form a_{m−r} … a_{m−1} for some 0 < r ≤ m. When k = n − 1 and C does not have an A-factor, eq. (11) becomes

H(n; C) = \overline{a}_{m−1} ∗ H(n − 1; C ∗ \overline{a}_{m−1})  when r(C) = 1, (12)
= 0 ∗ H(n − 1; C ∗ 0) ∪ 1 ∗ H(n − 1; C ∗ 1) otherwise. (13)

We build cyclic Gray codes for H(n; C) when h^{∗}(n; C) = 0, and Gray codes between fixed endpoints when |h^{∗}(n; C)| = 1. Given h^{∗}(n; C), Corollary 4.1 yields h^{∗}(n−1; C∗0) and h^{∗}(n−1; C ∗1). If C does not have an A-factor, then H(n; C) = Σ_{q}^{n} when r(C) > n because r(C) characters are needed to create an A-factor. We say that L contains the path [X, …, Z] if X, …, Z appears as a contiguous subsequence of L or L^{R}.

Theorem 4.1 Fix q = 2, m > 1 and A ∈ Σ_{2}^{m} such that A ends with two identical characters. Let n be in the range 2 ≤ n ≤ m. Then there exist strings S_{n}, T_{n}, X_{n}, Y_{n}, Z_{n}, and Z′_{n} such that for any C ∈ Σ_{2}^{∗} with no A-factor,

1. If r(C) = 1 and n ≥ 3, then there exists a Gray code for H(n; C) containing the path [X_{n}, Y_{n}, Z_{n}]. When h^{∗}(n; C) = 0, the Gray code is cyclic. Otherwise, |h^{∗}(n; C)| = 1, and the Gray code starts at S_{n} and ends at T_{n}.

2. If r(C) > 1 and n ≥ 2, then there exists a Gray code for H(n; C) containing the path [X_{n}, Y_{n}, Z′_{n}]. When h^{∗}(n; C) = 0, the Gray code is cyclic. Otherwise, |h^{∗}(n; C)| = 1, and the Gray code starts at S_{n} and ends at T_{n}.

For 2 ≤ n ≤ m, S_{n} and T_{n} have parity opposite that of A_{n} = a_{m−n} … a_{m−1}, and A_{n} ∈ H(n; C) implies S_{n}, T_{n} ∈ H(n; C).

Proof. Assume that A ends in 00; similar techniques apply if A ends in 11. We prove Parts 1 and 2 by induction on n using the recursive decomposition of eqs. (12) and (13), and using the strings

\begin{aligned}S_{n} & = & a_{m−n} … \overline{a}_{m−1} & X_{n} & = & 101^{n−2} \\ T_{n} & = & a_{m−n} … \overline{a}_{m−2}a_{m−1} & Y_{n} & = & 1^{n} \\ Z′_{n} & = & 01^{n−1} & Z_{n} & = & 1101^{n−3} \end{aligned}

Let C_{0} = C ∗ 0 and C_{1} = C ∗ 1. Basis. First consider when n = 2 and r(C) > 1. If r(C) > 2, then H(2; C) = Σ_{2}^{2}. If r(C) = 2 then H(2; C) = {01, 11, 10}. The Gray codes in these cases are 01, 11, 10, 00 and 01, 11, 10, respectively. These Gray codes satisfy Part 2.

Next consider when n = 3 and r(C) = 2, so C ends with a_{0} … a_{m−3}. By eq. (13)

H(3; C) = 0 ∗ H(2; C_{0}) ∪ 1 ∗ H(2; C_{1}).

Note that C_{0} ends with a_{0} … a_{m−2}, so r(C_{0}) = 1 and H(2; C_{0}) = {11, 10}. Since C_{1} ends with 1, r(C_{1}) ≥ 2. If r(C_{1}) = 2, then H(2; C_{1}) = {01, 11, 10}, and if r(C_{1}) > 2, then H(2; C_{1}) = Σ_{2}^{2}. In the former case, let L = 101, 111, 011, 010, 110. Then L contains the path [X_{3}, Y_{3}, Z′_{3}]. The fact that r(C_{1}) = 2 implies that C_{1} ends in a_{0} … a_{m−3}, so a_{m−3} = 1, and L runs between S_{3} and T_{3}. In the latter case, L = 101, 111, 011, 010, 110, 100 is a cyclic Gray code containing [X_{3}, Y_{3}, Z′_{3}]. Inductive step for Part 1. Suppose that n is in the range 3 ≤ n ≤ m, C ∈ Σ_{2}^{∗} has no A-factor, and r(C) = 1. Then H(n; C) = 1 ∗ H(n − 1; C_{1}) by eq. (12). Since C_{1} ends with 1, r(C_{1}) ≥ 2 and H(n − 1; C_{1}) falls into Part 2 of the theorem. Inductively assume that the theorem holds for H(n − 1; C_{1}).

Suppose h^{∗}(n; C) = 0, so h^{∗}(n − 1; C_{1}) = 0 also. By induction, there exists a cyclic Gray code L_{1} for H(n − 1; C_{1}) containing the path [X_{n−1}, Y_{n−1}, Z′_{n−1}] = [101^{n−3}, 1^{n−1}, 01^{n−2}]. Then 1 ∗ L_{1} is a Gray code for H(n; C) satisfying Part 1.

Next suppose |h^{∗}(n; C)| = 1, so |h^{∗}(n − 1; C_{1})| = 1 also. We can inductively find a Gray code L_{1} for H(n − 1; C_{1}) such that L_{1} starts at S_{n−1} and ends at T_{n−1}. Further, L_{1} contains the path [X_{n−1}, Y_{n−1}, Z′_{n−1}]. If a_{m−n} = 1, then 1 ∗ L_{1} satisfies Part 1. By Lemma 4.2, C_{1} must end with a_{0} … a_{m−n}, so a_{m−n} = 1. This concludes the inductive step for Part 1 of the theorem. Inductive step for Part 2. Suppose that n is in the range 3 ≤ n ≤ m, C ∈ Σ_{2}^{∗} has no A-factor, and r(C) ≥ 2. Inductively assume that the theorem holds for H(n−1; C_{0}) and H(n − 1; C_{1}). We separately examine when h^{∗}(n; C) = 0 (Case 2a), and when |h^{∗}(n; C)| = 1 (Case 2b). Case 2a. Suppose h^{∗}(n; C) = 0. By Corollary 4.1, both h^{∗}(n−1; C_{0}) and h^{∗}(n−1; C_{1}) are also zero. Note that r(C_{1}) ≥ 2 because C_{1} ends with 1. There is a cyclic Gray code L_{1} for H(n−1; C_{1}) containing the path [X_{n−1}, Y_{n−1}, Z′_{n−1}]. Also, there is a cyclic Gray code L_{0} for H(n − 1; C_{0}) containing the path [X_{n−1}, Y_{n−1}, U_{n−1}], where U_{n−1} = Z_{n−1} if r(C_{0}) = 1, and U_{n−1} = Z′_{n−1} otherwise. Since L_{0} and L_{1} both contain the path [X_{n−1}, Y_{n−1}], a Gray code L for H(n; C) can be formed by joining 0 ∗ L_{0} and 1 ∗ L_{1} by these strings as in Figure 3. Then L contains the path [1 ∗ Z′_{n−1}, 1 ∗ Y_{n−1}, 0 ∗ Y_{n−1}] = [X_{n}, Y_{n}, Z′_{n}], satisfying Part 2. Case 2b. Suppose |h^{∗}(n; C)| = 1. Let D = C ∗ \overline{a}_{m−n} and E = C ∗ a_{m−n}, so

H(n; C) = \overline{a}_{m−n} ∗ H(n − 1; D) ⋃ a_{m−n} ∗ H(n − 1; E).

Using Corollary 4.1, h^{∗}(n−1; D) = 0 and |h^{∗}(n−1; E)| = 1. The possibility that n = 3 and r(C) = 2 was considered in the basis. Inductively, there exists a cyclic Gray code L_{d} for H(n−1; D) containing the path [X_{n−1}, Y_{n−1}, U_{n−1}], where U_{n−1} = Z_{n−1} if r(D) = 1

[figure: 1 ∗ L_{1}; 0 ∗ L_{0}; …; …; 1 ∗ Z′_{n−1}; 1 ∗ Y_{n−1}; 1 ∗ X_{n−1}; …; …; 0 ∗ U_{n−1}; 0 ∗ Y_{n−1}; 0 ∗ X_{n−1}; If r(C_{0}) = 1, then U_{n−1} = 1101^{n−4}.; If r(C_{0}) > 1, then U_{n−1} = 01^{n−2}.]

Figure 3: Gray code construction for Case (2a)

[figure: a_{m−n} ∗ L_{e}; \overline{a}_{m−n} ∗ L_{d}; …; …; a_{m−n} ∗ S_{n−1}; a_{m−n} ∗ U′_{n−1}; a_{m−n} ∗ Y_{n−1}; a_{m−n} ∗ X_{n−1}; a_{m−n} ∗ T_{n−1}; …; …; \overline{a}_{m−n} ∗ U_{n−1}; \overline{a}_{m−n} ∗ Y_{n−1}; \overline{a}_{m−n} ∗ X_{n−1}; If r(D) = 1, then U_{n−1} = Z_{n−1}. Else U_{n−1} = Z′_{n−1}.; If r(E) = 1, then U′_{n−1} = Z_{n−1}. Else U′_{n−1} = Z′_{n−1}.]

Figure 4: Gray code construction for Case (2b)

and U_{n−1} = Z′_{n−1} otherwise. There also exists a Gray code L_{e} for H(n − 1; E) starting at S_{n−1} and ending at T_{n−1}. The Gray code L_{e} contains the path [X_{n−1}, Y_{n−1}, U′_{n−1}], where U′_{n−1} = Z_{n−1} if r(E) = 1 and U′_{n−1} = Z′_{n−1} otherwise.

Let L be the Gray code obtained from \overline{a}_{m−n} ∗ L_{d} and a_{m−n} ∗ L_{e} as shown in Figure

4. Then L starts and ends on the correct vertices, and it contains the path

[a_{m−n} ∗ U′_{n−1}, a_{m−n} ∗ Y_{n−1}, \overline{a}_{m−n} ∗ Y_{n−1}, \overline{a}_{m−n} ∗ U_{n−1}].

If a_{m−n} = 0, then D ends with 1, so r(D) > 1 and U_{n−1} = Z′_{n−1}. If a_{m−n} = 1, then E ends with 1, so r(E) > 1 and U′_{n−1} = Z′_{n−1}. In either case, L contains the path [X_{n}, Y_{n}, Z′_{n}]. This completes the inductive argument.

Note that S_{n} and T_{n} have parity opposite that of A_{n}. If C ∗ a_{m−n} … a_{m−1} does not have an A-factor, then neither does C ∗ a_{m−n} … \overline{a}_{m−1}. Likewise for C ∗ T_{n}. □

By considering the small n cases not covered by Theorem 4.1, we get the following.

Corollary 4.2 Fix q = 2, m > 1 and A ∈ Σ_{2}^{m} such that A ends with two identical characters. For any n, 1 ≤ n ≤ m, and for any C ∈ Σ_{2}^{∗} with no A-factor, there is a Gray code for H(n; C). When h^{∗}(n; C) = 0, the Gray code is cyclic. Otherwise, its endpoints are independent of C and of equal parity.

Proof. We need only consider when n ≤ 2 and Theorem 4.1 does not apply. □

In the next section, we present results analogous to Theorem 4.1 and Corollary 4.2 for even q ≥ 4.

4.3 Gray codes when q ≥ 4 is even and n ≤ m

In this section, we construct Gray codes for H(n; C) when 1 ≤ n ≤ m and q ≥ 4 is even. For x ∈ Σ_{q}, we defined \overline{x} ≡ x + 1 mod q. We similarly define \underline{x} ≡ x − 1 mod q. Recall from Section 1 that when q is even, two strings are “similar” if they differ at one position, and by ±1 mod q in that position.

Theorem 4.2 Fix an even q ≥ 4, m > 0 and A ∈ Σ_{q}^{m}. For any n, 1 ≤ n ≤ m, there exist strings S_{n}, T_{n}, X_{n}, Y_{n}, and Z_{n} such that for any C ∈ Σ_{q}^{∗} with no Afactor, there exists a Gray code for H(n; C) containing the path [X_{n}, Y_{n}, Z_{n}]. When h^{∗}(n; C) = 0, the Gray code is cyclic, and when |h^{∗}(n; C)| = 1, the Gray code is from S_{n} to T_{n}. Further, S_{n} and T_{n} have parity opposite that of A_{n} = a_{m−n} … a_{m−1}, and A_{n} ∈ H(n; C) implies S_{n}, T_{n} ∈ H(n; C).

Proof. Let x satisfy |x − a_{m−1}| ≥ 2. We argue inductively on n using the strings

S_{n} = a_{m−n} … \overline{a}_{m−1}  X_{n} = \underline{x}x^{n−1}
T_{n} = a_{m−n} … \underline{a}_{m−1}  Y_{n} = x^{n}
Z_{n} = \overline{x}x^{n−1}

Let C be a string over Σ_{q} with no A-factor. When r(C) > 1, H(1; C) = Σ_{q}. When r(C) = 1, H(1; C) = Σ_{q} \\{a_{m−1}\}. Note that \{\underline{x}, x, \overline{x}\} ⊆ H(1; C). The Gray codes in these cases are, respectively, a_{m−1}, \overline{a}_{m−1}, …, \underline{a}_{m−1} and \overline{a}_{m−1}, …, \underline{a}_{m−1}. These Gray codes satisfy the theorem.

Suppose that 1 < n ≤ m and C ∈ Σ_{q}^{∗} has no A-factor. From (11) we obtain

H(n; C) = ⋃_{y∈H(1;C)} y ∗ H(n − 1; C ∗ y).

For each y ∈ H(1; C), assume the theorem holds for H(n − 1; C ∗ y). Let L_{y} be a Gray code for H(n − 1; C ∗ y) containing the path [X_{n−1}, Y_{n−1}, Z_{n−1}]. These Gray codes exist inductively, and are either cyclic, or between S_{n} and T_{n}.

Suppose h^{∗}(n; C) = 0. By Corollary 4.1, h^{∗}(n − 1; C ∗ y) = 0 for all y ∈ H(1; C), so the Gray codes L_{y} are cyclic. The y ∗ L_{y} can be connected as in Figure 5 (a) to form a Gray code for H(n; C). First, join all y ∗ L_{y} using the string y ∗ Y_{n−1}, ensuring that [\underline{x}∗Y_{n−1}, x∗Y_{n−1}, \overline{x}∗Y_{n−1}] is a subpath. This can be done because \{\underline{x}, x, \overline{x}\} ⊆ H(1; C). Next, use the outer two strings on the fixed path to finish the joining the y ∗ L_{y}. This strategy can be employed independent of r(C).

A similar strategy works when |h^{∗}(n; C)| = 1. In this case, by Corollary 4.1, |h^{∗}(n − 1; C ∗ a_{m−n})| = 1 and h^{∗}(n − 1; C ∗ y) = 0 for y ∈ H(1; C)\{a_{m−n}}. For

[figure: \underline{x}x^{n−2}; x^{n−1}; \overline{x}x^{n−2}; \underline{x} ∗ L\underline{x}; x ∗ L_{x}; \overline{x} ∗ L\overline{x}; ⋮; (a) when h^{∗}(n; C) = 0; \underline{x}x^{n−2}; x^{n−1}; \overline{x}x^{n−2}; \underline{x} ∗ L\underline{x}; x ∗ L_{x}; \overline{x} ∗ L\overline{x}; ⋮; (a) when |h^{∗}(n; C)| = 1]

Figure 5: Gray code construction when q ≥ 4 is even.

y ∈ H(1; C), y ≠ a_{m−n}, L_{y} is cyclic, while L_{a_{m−n}} goes from S_{n−1} to T_{n−1}. Connect all of the y ∗ L_{y} using y ∗ Y_{n−1}. Then, as before, use the outer two strings to finish joining the y ∗ L_{y}. Refer to Figure 5 (b) for an illustration.

Observe that S_{n} and T_{n} have parity opposite that of A_{n}, and if C ∗ A_{n} = C ∗ a_{m−n} … a_{m−1} has no A-factor, then neither do C ∗ S_{n} and C ∗ T_{n}. □

As with Theorem 4.1, we get a corollary to Theorem 4.2.

Corollary 4.3 Fix an even q ≥ 4, m > 0 and A ∈ Σ_{q}^{m}. For any n, 1 ≤ n ≤ m, and any C ∈ Σ_{q}^{∗} with no A-factor, there is a Gray code for H(n; C). When h^{∗}(n; C) = 0, the Gray code is cyclic. Otherwise, its endpoints are independent of C and of equal parity.

The techniques used to construct Gray codes in Theorems 4.1 and 4.2 do not apply as n is increased. In particular, Lemma 4.2 and Corollary 4.1 are not true for all n > m. For larger n, a new construction technique must be employed.

In Section 3.1 we showed that, when q is even, unless A is either t.a. or periodic with a t.a. minimal base, then F(n) has infinite parity problems. In Section 4.4, Gray codes for F(n) are constructed for all n when A is t.a and q is even. When A is periodic with a t.a. minimal base and q is even, Gray codes for F(n) also exist for all n ≥ 0. The proof of this result is in Section 4.5.

4.4 A trivially autocorrelated

Recall that A is trivially autocorrelated, or t.a., if AA = 10 ⋯ 0, or, equivalently, if r(A) = m. A trivially autocorrelated string can overlap itself in only the trivial ways. In this section, we construct Gray codes for F(n) for all n ≥ 0 when A is t.a. and q is even. The main result of this section is Theorem 4.3.

Theorem 4.3 Fix an even q ≥ 2, m > 0, and a t.a A ∈ Σ_{q}^{m}. For all n ≥ 1 there is a Gray code for F(n). If f^{∗}(n) = 0, and either A ∉ {01, 10} or q ≥ 4, then there is a cyclic Gray code.

We prove Theorem 4.3 a little later. First, we examine the parity difference of H(m; C).

Lemma 4.3 Fix an even q ≥ 2, m > 0 and a t.a A ∈ Σ_{q}^{m}. For any C ∈ Σ_{q}^{∗} with no A-factor, |h^{∗}(m; C)| = 1.

Proof. Let C ∈ Σ_{q}^{∗} be a string with no A-factor. It is clear that A ∉ H(m; C). By Lemma 4.2, if, for all x ≠ a_{m−1}, A′ = a_{0} … a_{m−2}x ∈ H(m; C), then |h^{∗}(m; C)| = 1. Suppose D = C ∗A′ has an A-factor. Any A factor in D must overlap A′ in a non-trivial way, which contradicts the hypothesis that A is t.a. Therefore, C ∗ A′ does not have an A-factor and the lemma is proved. □

We now prove Theorem 4.3. Recall Lemma 4.1 of Section 4.1. First suppose that A is any non-empty t.a. string and q ≥ 4. Then Corollary 4.3 provides Gray codes for H(n; C) for all n, 1 ≤ n ≤ m, and all C with no A-factor. It provides cyclic Gray codes when h^{∗}(n; C) = 0. This same corollary, in conjuction with Lemma 4.3 above, also proves the existence of strings S and T, of equal parity, such that for any D with no A-factor, there is a Gray code for H(m; D) from S to T. Hence, conditions (1) and

(2) of Lemma 4.1 are satisfied when k = m. We can therefore conclude that for all n ≥ 1 and for all C with no A-factor, there is a Gray code for H(n; C). Further, there is a cyclic Gray code when h^{∗}(n; C) = 0. Since F(n) = H(n; ϵ), Theorem 4.3 is proved when q ≥ 4 is even.

Next suppose that q = 2 and A is a t.a. string ending in two identical characters. In this case, Corollary 4.2 and Lemma 4.3 prove that, when k = m, conditions (1) and (2) of Lemma 4.1 are again satisfied. Thus, for all n ≥ 1 and all C with no A-factor, there is a Gray code for H(n; C). There is a cyclic Gray code when h^{∗}(n; C) = 0. Again, Theorem 4.3 follows by F(n) = H(n; C).

We are left to consider when q = 2 and A is t.a. but does not end in two identical characters. We claim that any t.a. binary string of length m ≥ 3 has either a_{m−2} = a_{m−1} or a_{0} = a_{1}. To see this, suppose A is a t.a. binary string of length m ≥ 3 with a_{0} ≠ a_{1} and a_{m−2} ≠ a_{m−1}. WLOG, say a_{0} = 0. If a_{m−1} = 0, then bit (m − 1) of AA is one. If a_{m−1} = 1, then A begins and ends with 01, so bit (m − 2) of AA is one. In either case, A is not t.a.

So every t.a. binary string of length m ≥ 3 must begin or end with two identical characters. We have already considered when A ends with two identical characters, so suppose that A begins with two identical characters, and let Z be the reverse of A. Then Z is also t.a., and Z ends with two identical characters. For n ≥ 1, we can find a Gray code L for the strings with no Z-factor. Reversing every string on L gives a Gray code for F(n), the strings with no A-factor.

We have now proved Theorem 4.3 in all cases except when q = 2 and m < 3. The only t.a. binary strings of length less than or equal to two are {0, 1, 01, 10}. When A = 0, F(n) = {1^{n}}. When A = 01, F(n) = {1^{k}0^{n−k}|0 ≤ k ≤ n}. When A = 1 or A = 10, the set F(n) is similarly defined. Gray codes in these cases are clear and unique. If A ∈ {01, 10}, then no cyclic Gray code exists even when the parity difference is zero. This completes the proof of Theorem 4.3.

In Section 4.5, we prove an analogous result when A is periodic with a t.a. minimal base.

4.5 A periodic with a t.a. minimal base

In this section, we examine H(n; C) when A = B ∗ ⋯ ∗ B and B is t.a. Throughout Section 4.5, B refers to the minimal base of A and p to the minimal period. Again, q ≥ 2 is assumed even. The overall strategy employed in this section is identical to that of the previous section. We identify k such that |h^{∗}(k; C)| = 1 independent of C. We then apply Lemma 4.1 to obtain Gray codes for all n.

As seen in Section 4.4, when A is t.a. and k = m, |h^{∗}(k; C)| = 1 independent of C. When A is periodic with a t.a. minimal base, this is no longer true, as we see below.

Lemma 4.4 Fix an even q ≥ 2, m > 0 and a periodic A ∈ Σ_{q}^{m} with a t.a minimal base B. For any C ∈ Σ_{q}^{∗} with no A-factor, h^{∗}(m; C) = 0 if and only if C ends with B. Otherwise, |h^{∗}(m; C)| = 1.

Proof. Let C ∈ Σ_{q}^{∗} be any string with no A-factor. By Lemma 4.2 with n = m, h^{∗}(m; C) = 0 if and only if A′ = a_{0} … a_{m−2}x ∉ H(m; C) for some x ≠ a_{m−1}. Suppose C ∗ A′ has an A-factor. Some B-term of this A-factor must overlap the first B-term of A′. Since B is t.a., the B-terms must overlap completely. This implies that C ends with B. Otherwise, A′ ∈ H(m; C) for all x ≠ a_{m−1}, and |h^{∗}(m; C)| = 1. □

Suppose that A ∈ Σ_{q}^{m} is periodic with a t.a. minimal base and with minimal period p. By the previous lemma, there cannot exist strings S and T such that for any C with no A-factor, there is a Gray code for H(m; C) from S to T. However, we will show that such strings S and T do exist for H(m + p; C). As an intermediate step, we extend Theorems 4.1 and 4.2 to provide Gray codes for H(n; C) for n in the range m < n ≤ m + p. This is done below.

Lemma 4.5 Fix an even q ≥ 2, m > 0, and a periodic A ∈ Σ_{q}^{m} with a t.a. minimal base B and with minimal period p. When q = 2, further assume that m ≥ 2 and a_{m−2} = a_{m−1}. For any C ∈ Σ_{q}^{∗} with no A-factor and any n, 1 ≤ n ≤ p, there is a Gray code for H(m + n; C). When h^{∗}(m + n; C) = 0, there is a cyclic Gray code. Otherwise, |h^{∗}(m + n; C)| = 1, and there is a Gray code between two strings independent of C and of equal parity.

Proof. Let C ∈ Σ_{q}^{∗} be a string with no A-factor, and let n be in the range 1 ≤ n ≤ p. By Corollaries 4.2 and 4.3, for 1 ≤ l ≤ m, there exist strings S_{l} and T_{l}, of equal parity, such that H(l; C) has a Gray code between S_{l} and T_{l} whenever |h^{∗}(l; C)| = 1. Define S and T by S = S_{n} ∗ S_{m} and T = T_{n} ∗ T_{m}. We show that when |h^{∗}(n + m; C)| = 1, there is a Gray code for H(n + m; C) between S and T. Observe that S and T have equal parity.

For a recursive decomposition of H(m + n; C), we use eq. (11) with k = m. Since n ≤ p, there exists at most one D ∈ H(n; C) such that C ∗ D ends with B, namely A_{n} = b_{p−n} … b_{p−1}. By Lemma 4.4, for at most one D ∈ H(n; C) does h^{∗}(m; C∗D) = 0. When C ∗ D does not end with B, there is a Gray code L_{D} for H(m; C ∗ D) between S_{m} and T_{m}. When C ∗ D ends with B, there is a cyclic Gray code L_{D} for H(m; C ∗ D). Consider: when |h^{∗}(n; C)| = 1 (Case 1), and when h^{∗}(n; C) = 0 (Case 2). Case 1. Assume |h^{∗}(n; C)| = 1. By Corollaries 4.2 and 4.3, there exists a Gray code L′ = D_{0}, …, D_{N−1} for H(n; C) between S_{n} and T_{n}. Note that N is odd. By Lemma 4.2, C ends with a_{0} … a_{m−n−1}, so A_{n} ∉ H(n; C). Therefore, for no D in H(n; C) does C ∗ D end with B. By Lemma 4.4, |h^{∗}(m; C ∗ D_{i})| = 1 for all D_{i}. For each i, we can find a Gray code L_{i} for H(m; C ∗ D_{i}) from S_{m} to T_{m}. Let

L = D_{0} ∗ L_{0}, D_{1} ∗ L_{1}^{R}, ⋯, D_{N−1} ∗ L_{N−1}.

Then L is a Gray code for H(m + n; C) from S to T. Case 2. Assume h^{∗}(n; C) = 0. By Corollaries 4.2 and 4.3, there is a cyclic Gray code L′ = D_{0}, …, D_{N−1} for H(n; C). We have two subcases to consider: when there exists a D_{i} such that C ∗ D_{i} ends with B, and when no such D_{i} exists. In the latter case, by Lemma 4.4, |h^{∗}(m; C ∗ D_{i})| = 1 for all D_{i}. There exists a Gray code L_{i} for each H(m; C ∗ D_{i}) from S_{m} to T_{m} by Corollaries 4.2 and 4.3. Then

L = D_{0} ∗ L_{0}, D_{1} ∗ L_{1}^{R}, …, D_{N−1} ∗ L_{N−1}^{R}

is a cyclic Gray code for H(m + n; C).

Next, consider when there exists an i such that C ∗ D_{i} ends with B. WLOG we can assume that i = 0, so D_{0} = A_{n}. First, assume that either n ≥ 2 or q ≥ 4. By Theorems 4.1 and 4.2, there exist strings X_{m}, Y_{m} ∈ Σ_{q}^{m} such that for all i, there is a Gray code for H(m; C ∗D_{i}) containing the path [X_{m}, Y_{m}]. When i = 0, there is a cyclic Gray code, and for all other i, there is a Gray code from S_{m} to T_{m}. By Theorems 4.1 and 4.2, S_{n} and T_{n} are in H(n; C) because A_{n} = D_{0} ∈ H(n; C). Further, S_{n} and T_{n} have parity opposite that of A_{n}.

Let l and r be such that D_{l} = S_{n} and D_{r} = T_{n}. WLOG assume l < r. By the parity condition, l and r must be odd. The construction of the Gray code for H(m + n; C) has three phases. Refer to Figure 6 for a graphical illustration. We refer to X_{m} and Y_{m} as special strings.

In phase one, we construct a Gray code for ∪_{i=0}^{l}D_{i} ∗ H(m; C ∗ D_{i}). Starting with the S_{m} end of L_{l}, follow L_{l} until reaching the first special string. Then jump to L_{l−1} and move to S_{m} or T_{m}, whichever end is reachable without passing through the other special string. At this endpoint, jump to L_{l−2}, and continue this process of using only the part of L_{i} between an endpoint its closest special string. At D_{0}, follow the cyclic Gray code L_{0} between the special strings, and then work back up the L_{i} using the part of L_{i} not used on the way down. Continue this process until the T_{m} end of L_{l}

[figure: \underline{Phase 1}; \underline{Phase 2}; \underline{Phase 3}; S_{m}; T_{m}; D_{0} ∗ L_{0}; D_{l} ∗ L_{i}; D_{r} ∗ L_{r}; D_{r+1} ∗ L_{r+1}; D_{1} ∗ L_{1}; D_{l−1} ∗ L_{l−1}; D_{N−1} ∗ L_{N−1}; X_{m}; Y_{m}; …; …; …; …; …; …]

Figure 6: Constructing a Gray code for H(m + n; C) when 1 ≤ n ≤ p

is reached. This constructs a Gray code for ∪_{i=0}^{l}D_{i} ∗ H(m; C ∗ D_{i}) from S_{n} ∗ S_{m} to S_{n} ∗ T_{m}.

In phase two, a Gray code for ∪_{i=l+1}^{r−1}D_{i} ∗ H(m; C ∗ D_{i}) is constructed. The Gray code begins with D_{l+1} ∗ T_{m} and ends with D_{r−1} ∗ S_{m}. The Gray code is defined by

D_{l+1} ∗ L_{l+1}^{R}, D_{l+2} ∗ L_{l+2}, …, D_{r−1} ∗ L_{r−1}^{R}.

Phase three constructs a Gray code for ∪_{i=r}^{N−1}D_{i} ∗ H(m; C ∗ D_{i}) from T_{n} ∗ S_{m} to T_{n} ∗ T_{m}. This Gray code is constructed in a similar manner to the phase one Gray code. Starting with S_{m} in L_{r}, follow L_{r} from S_{m} to the nearest special string, then jump to L_{r+1}. In L_{r+1}, move to the endpoint reachable without passing through the other special string, and jump to L_{r+2}. When L_{N−1} is reached, use it to turn around by going between S_{m} and T_{m}. Recall that r is odd and N is even, so this is possible. Then travel back down the unused portions of the L_{i} until reaching D_{r} ∗ T_{m}.

Concatenating together the Gray codes from each phase yields a Gray code for H(m + n; C) from S to T.

We have not yet considered when q = 2 and n = 1. It is a simple matter to get a Gray code for H(m + 1; C) from Gray codes for H(m; C_{0}) and H(m; C_{1}). We omit the details. In all cases, when h^{∗}(m + n; C) = 0, the Gray codes constructed are cyclic. Otherwise, the Gray codes are between S and T. □

Suppose A ∈ Σ_{q}^{m} is periodic with minimal period p and with a t.a. minimal base. Let C ∈ Σ_{q}^{∗} be a string with no A-factor. The preceding lemma supplies a Gray code for H(n; C) for n in the range m < n ≤ m + p. This result can be combined with Corollaries 4.2 and 4.3 to get Gray codes for H(n; C) whenever 1 ≤ n ≤ m + p. We next show that at the upper bound of this range, there is always a Gray code between two endpoints independent of C.

Lemma 4.6 Fix an even q ≥ 2, m > 0, and a periodic A ∈ Σ_{q}^{m} with a t.a. minimal base and with minimal period p. If C ∈ Σ_{q}^{∗} has no A-factor, then |h^{∗}(m + p; C)| = 1.

Proof. As in the proof of Lemma 4.2, we pair even and odd strings. Say C ∈ Σ_{q}^{∗} has no A-factor, and let D = d_{0} … d_{m+p−1} be a string in H(m + p; C). If D does not end with A′ = a_{0} … a_{m−2}x, where x is the mate of a_{m−1}, then pair D with the string obtained by replacing the last character of D with its mate.

Let S denote the set of unpaired strings in H(m + p; C). We claim each D ∈ S can be paired with the string obtained by replacing the character in position (p − 1) of D with its mate unless D also begins with B′ = b_{0} … b_{p−2}x, where x is the mate of b_{p−1} = a_{m−1}. Suppose D = d_{0} … d_{p−1} ∗A′ ∈ S but E = D′ ∗A′ = d_{0} … d_{p−2}y ∗A′ ∉ S, where y is the mate of d_{p−1}. Every A-factor in C ∗ E must use last character of D′. If the A-factor of C ∗ E ends on this character, then D′ = B. If a B-term of the A-factor overlaps the first B-term of A′, then the B-terms must overlap completely. Again, D′ = B. Thus, the only possible unmatched string is B′ ∗ A′.

We claim B′ ∗ A′ ∈ H(m + p; C) for all C ∈ Σ_{q}^{∗} with no A-factor. If D = C ∗ B′ ∗ A′ contained an A-factor, then either the A-factor is in C ∗ B′, or the A-factor overlaps the A′-suffix of D. In either case, B overlaps itself in a non-trivial way. Thus B′ ∗ A′ ∈ H(m + p; C), and h^{∗}(m + p; C) is ±1 depending on the parity of B′ ∗ A′. □

We now prove the main result of this section.

Theorem 4.4 Fix an even q ≥ 2, m > 0, and a periodic A ∈ Σ_{q}^{m} with a t.a. minimal base. For n ≥ 1, there exists a Gray code for F(n). When f^{∗}(n) = 0, there is a cyclic Gray code.

Proof. This proof is similar to the proof of Theorem 4.3 in Section 4.4. Suppose that A ∈ Σ_{q}^{m} is periodic with a t.a. minimal base B and with minimal period p, and that q ≥ 4 is even. Say C ∈ Σ_{q}^{∗} has no A-factor. Refer to Lemma 4.1 of Section 4.1. By Corollary 4.3 and Lemma 4.5, there exist a Gray code for H(n; C) for all 1 ≤ n ≤ m + p. There is a cyclic Gray code whenever h^{∗}(n; C) = 0. This satisfies condition (1) of Lemma 4.1. By Lemmas 4.5 and 4.6, for any D with no A-factor, there exist a Gray code for H(m + p; D) between two strings independent of D and of equal parity. This satisfies condition (2) of Lemma 4.1. Therefore, for all n ≥ 1 and for all C with no A-factor, there exists a Gray code for H(n; C). This Gray code is cyclic when h^{∗}(n; C) = 0. This, of course, implies the Gray code result for F(n) = H(n; ϵ).

Now suppose q = 2. If A ends in two identical characters, then the arguments of the preceding paragraph can be repeated by replacing Corollary 4.3 with Corollary 4.2. We have not yet considered when A is periodic with a t.a. minimal base and A does not end in two identical characters. As in Section 4.4, if p ≥ 3, then A either begins or ends in two identical characters. If A begins with two identical characters, then Gray codes for F(n) can be found by considering the reverse of A.

We are left to consider when p ≤ 2. If p = 2, then B ∈ {01, 10}. In this case, neither A nor its reverse satisfies the conditions of Corollary 4.2. If p = 1 and m ≥ 2, then A satisfies the conditions of Corollary 4.2 and the conclusions follow as before.

The remaining possibility is that B ∈ {01, 10}. To construct Gray codes for H(n; C) in this case requires complicating the constructions in Section 4. In particular, there are more individual cases in the basis. The details can be found in Appendix A, and the conclusions of the theorem still follow. □

When q is even, we have constructed Gray codes for F(n) for all n ≥ 1 when A is t.a. or A is periodic with a t.a. minimal base. The results of Section 3.1 prove that these are the only A for which Gray codes are always possible.

5 Conclusions

In this paper, we have investigated the existence of Gray codes for A-free strings. We have determined for which q and A Gray codes for F(n) are always possible, and in the even q case, we have constructed the Gray codes. When q is odd, it remains open to construct Gray codes for F(n) when no parity problems exist. Recall that when q is odd, two strings are similar if they differ in one position, and by ±1 in that position, where the addition is not modulo q. If modular arithmetic were used, the resulting auxiliary graph G_{q}(F(n)) would not be bipartite, thus invalidating the parity arguments of Section 3. Note that when q is odd, it is possible for the graph G_{q}(F(n)) to be disconnected. For example, consider when q = 5, A = 2, and n ≥ 1. However, we conjecture that, with few exceptions, there do exist a Gray codes for F(n) when F(n) does not have infinite parity problems.

Similarly, we can consider removing the modular arithmetic in the even q case. Again, we conjecture that, for the most part, there exist Gray codes for F(n) when F(n) does not have infinite parity problems. We can also consider using modular arithmetic in the odd q case. The parity arguments of Section 3 would no longer apply, so Gray codes may exist in situations not covered in Section 3

As mentioned in Section 1, the A-free string concept has been defined more generally. It would be interesting to develop conditions on a set A of strings such that F(n; A) has a Gray code for all n ≥ 0. In this general case, even if q is even and we use modular addition, the graph G_{q}(F(n)) need not be connected. For example, consider when q = 2, A = {01, 10}, and n ≥ 2.

There have also been many variations on the A-free string concept. Given A = {A_{1}, …, A_{p}} and a vector m = (m_{1}, …, m_{p}), let F(n; A; m) denote the set of X ∈ Σ_{q}^{n} such that, for 1 ≤ i ≤ p, X has m_{i} occurrences of A_{i}. Goulden and Jackson [3] prove that F(n; A; m) has a rational generating function. Zeilberger [12] and Goulden and Jackson [2] have studied similar sets when each i ∈ Σ_{q} is restricted to appear a certain number of times. Zeilberger [13] has also studied the concept of A-free strings when A cannot appear as a subsequence (not necessarily contiguous). Gray codes for these variations deserve future attention.

We briefly mention the topic of generating A-free strings. Given A, one can define a deterministic finite automaton M so that M accepts ∪_{n}F(n; A) [10]. Once we have a DFA for a language, generating its elements is a simple procedure.

The enumeration and generation of objects with restricted subobjects is an area rich for study. If strings are genetic sequences and certain subsequences are “diseased,” what is the probability of being disease-free? How does one efficiently generate all graphs that do not contain certain subconfigurations? How many ways can G be colored so that there does not exist a unicolored edge? These and many other problems can be characterized as enumerating and generating sets of objects with forbidden subobjects. As seen in this paper, introducing a Gray code requirement to the generation problem can complicate and enrich even the simple examples.

References

[1] Martin Gardner. On paradoxical situations that arise from nontransitive relations. Scientific American, 231(4):120–125, 1974.

[2] I. P. Goulden and D. M. Jackson. An inversion theorem for cluster decompositions of sequences with distinguished subsequences. Journal of the London Mathematical Society, 20:567–576, 1979.

[3] I. P. Goulden and D. M. Jackson. Combinatorial Enumeration. John Wiley & Sons, 1983.

[4] Leo J. Guibas. Periodicities in strings. In Alberto Apolstolico and Zvi Galil, editors, Combinatorial Algorithms on Words, pages 257–269. Springer-Verlag, 1984.

[5] Leo J. Guibas and Andrew M. Odlyzko. Periods in strings. Journal of Combinatorial Theory A, 30:19–42, 1981.

[6] Leo J. Guibas and Andrew M. Odlyzko. String overlaps, pattern matching, and nontransitive games. Journal of Combinatorial Theory A, 30:183–208, 1981.

[7] Ki Hang Kim, Mohan S. Putcha, and Fred W. Rousch. Some combinatorial properties of free semigroups. Journal of the London Mathematical Society, (2) 16:397– 402, 1977.

[8] Andrew M. Odlyzko. Enumeration of strings. In Alberto Apostolico and Zvi Galil, editors, Combinatorial Algorithms on Words, pages 205–228. Springer-Verlag, 1984.

[9] George Pólya and Gabor Szegö. Problems and Theorems in Analysis, volume II. Springer-Verlag, 1976.

[10] Howard Straubing. Applications of the theory of automata in enumeration. Discrete Mathematics, 64:269–279, 1987.

[11] Herbert S. Wilf. Generatingfunctionology. Academic Press, Inc., 1990.

[12] Doron Zeilberger. Enumerating words by their number of mistakes. Discrete Mathematics, 34:89–91, 1981.

[13] Doron Zeilberger. Enumerating totally clean words. Discrete Mathematics, 64:313–315, 1987.

A Appendix: A Special Case Construction

In the main body of this paper, we classified A ∈ Σ_{2}^{∗} such that, when q = 2, F(n; A) either had infinite parity problems, or F(n; A) had no parity problems. Further, for most of the A for which F(n; A) had no parity problems, Gray codes for F(n; A) were constructed for all n ≥ 0. When A is periodic with minimal base 01 or 10, we proved that F(n; A) had no parity problems, but we did not provide the Gray code construction. In this appendix, we remedy the situation by supplying the construction.

We continue to use A = a_{0} … a_{m−1} to denote the excluded substring, where m denotes the length of A. For this appendix, we assume that A is periodic with minimal base 10. Hence, m ≥ 4. If the minimal base of A were 01, then a Gray code for F(n; A) is found by reversing all of the strings on a Gray code for F(n; A^{R}).

We actually construct Gray codes for the set H(n; C), thus implying Gray codes for F(n) = H(n; ϵ). As in Section 4, the construction of Gray codes for H(n; C) has three stages: when n ≤ m, when m < n ≤ m + 2, and when n > m + 2. Gray codes for H(n; C) when n ≤ m are constructed in Section A.1. Gray codes for the latter two stages are described in Section A.2.

A.1 Gray codes when n ≤ m

In this section, we construct Gray codes for H(n; C) for all C with no A-factor and all n ≤ m. Lemma A.1, below, provides most of the Gray codes. This lemma is analogous to Theorem 4.1 of Section 4.

Lemma A.1 Fix q = 2, m ≥ 4 even, and let A be the periodic string of length m with minimal base 10. Let n be in the range 4 ≤ n ≤ m. There exist strings S_{n}, T_{n}, V_{n}, W_{n}, X_{n}, Y_{n}, and Z_{n} such that for any C ∈ Σ_{2}^{∗} with no A-factor,

1. If r(C) = 1 and n ≥ 5, then there exists a Gray code for H(n; C) containing the path [V_{n}, W_{n}, X_{n}]. When h^{∗}(n; C) = 0, the Gray code is cyclic. Otherwise, |h^{∗}(n; C)| = 1, and the Gray code starts at S_{n} and ends at T_{n}.

2. If r(C) = 2 and n ≥ 4, then there exists a Gray code for H(n; C) containing the path [Y_{n}, W_{n}, Z_{n}]. When h^{∗}(n; C) = 0, the Gray code is cyclic. Otherwise, |h^{∗}(n; C)| = 1, and the Gray code starts at S_{n} and ends at T_{n}.

3. If r(C) > 2 and n ≥ 4, then there exists a Gray code for H(n; C) containing the path [V_{n}, W_{n}, Y_{n}]. When h^{∗}(n; C) = 0, the Gray code is cyclic. Otherwise, |h^{∗}(n; C)| = 1, and the Gray code starts at S_{n} and ends at T_{n}.

Proof. Let C_{0} = C ∗ 0 and C_{1} = C ∗ 1. We argue by induction on n using the strings

S_{n} = a_{m−n} … \overline{a}_{m−1}  X_{n} = 1101^{n−3}
T_{n} = a_{m−n} … \overline{a}_{m−2}a_{m−1}  Y_{n} = 01^{n−1}
V_{n} = 101^{n−2}  Z_{n} = 11101^{n−4}
W_{n} = 1^{n}

Basis. The basis includes when n = 4 and r(C) > 1, when n = 5 and 2 ≤ r(C) ≤ 3, and when n = 6 and r(C) = 3. First consider when n = 4. If r(C) > 4, then

r(C) > 4 r(C) = 4 r(C) = 3 r(C) = 3 r(C) = 2
A ≠ 1010 A = 1010
0000  \underline{1011}  0000  \underline{1011}  0000
0010  \underline{1111}  0010  \underline{1111}  0100
0110  \underline{0111}  0110  \underline{0111}  1100
1110  0011  1110  0110  1101
1010  0001  1010  1110  0101
1000  1001  1000  1100  0001
1100  1101  1100  1101  0011
0100  0101  1101  1001  \underline{0111}
0101  0100  1001  0001  \underline{1111}
1101  0000  \underline{1011}  0011  \underline{1110}
1001  0010  \underline{1111}  0010  0110
\underline{1011}  0110  \underline{0111}  0000  0010
\underline{1111}  1110  0011  1000
\underline{0111}  1100  0001
0011  1000

0001

Table 1: Gray codes for H(4; C) in basis

H(4; C) = Σ_{2}^{4}. If r(C) = 4, then H(4; C) = Σ_{2}^{4} \{1010}. Suppose that r(C) = 3. If A ≠ 1010, then H(4; C) = Σ_{2}^{4} \{010b}, where 010b represents the strings in Σ_{2}^{4} with prefix 010. If A = 1010, then H(4; C) = Σ_{2}^{4} \{010b, 1010}. Finally, when r(C) = 2, H(4; C) = Σ_{2}^{4}\{10bb}. Whenever |h^{∗}(4; C)| = 1, the starting and ending points of the Gray code must be 1011 and 1000. Gray codes for these cases are given in Table 1. The strings on the specified subpath are underlined.

Next consider when n = 5. Note that m ≥ 6 because m ≥ n = 5 and m is even. If r(C) = 2, then H(5; C) = Σ_{2}^{5}\{10bbb}. If r(C) = 3, then H(5; C) = Σ_{2}^{5}\{010bb}. Gray codes for H(5; C) when r(C) = 2, 3 are given in Table 2.

We leave the case when n = 6 and r(C) = 3 as an exercise for the reader. Again, m ≥ n = 6. One must separately consider when A = 101010 and when A ≠ 101010.

For any k ≤ n,

H(n; C) = ⋃_{D∈H(n−k;C)} D ∗ H(k; C ∗ D).  (14)

The inductive steps use equation (14) when k = n − 1 and when k = n − 2.

Inductive step for Part 1. Let C ∈ Σ_{2}^{∗} be a string with no A-factor and with r(C) = 1. Let n satisfy 5 ≤ n ≤ m. Then H(n; C) = 1 ∗ H(n − 1; C_{1}), and r(C_{1}) = m − 1 > 2. By induction, there is a Gray code L_{1} for H(n − 1; C_{1}) containing the path [V_{n−1}, W_{n−1}, Y_{n−1}] = [101^{n−3}, 1^{n−1}, 01^{n−2}]. Note that L = 1 ∗ L_{1} contains the path [1101^{n−3}, 1^{n}, 101^{n−2}] = [X_{n}, W_{n}, V_{n}]. If L_{1} is cyclic, then L is cyclic and we are done. Otherwise, h^{∗}(n; C) = 1. In this case, |h^{∗}(n − 1; C_{1})| = 1, and L_{1} is between S_{n−1} and T_{n−1} by induction. By Lemma 4.2, C_{1} ends with a_{0} … a_{m−n}, so a_{m−n} = 1. Thus, L

r(C) = 2  r(C) = 3
00000 \underline{01111} 01010 00000 11101 10010
00001 \underline{11111} 01011 00001 11100 10011
00011 \underline{11101} 01001 00011 10100 10001
00010 11100 01000 00010 10101 11001
00110 11000  00110 \underline{10111} 11011
00111 11001  00111 \underline{11111} 11010
00101 11011  00110 \underline{01111} 11000
00100 11010  00100 01110 10000
01100 11110  01100 11110
01101 01110  01101 10110

Table 2: Gray codes for H(5; C) in basis

starts and ends on the correct strings.

Inductive step for Part 2. Let C ∈ Σ_{2}^{∗} be a string with no A-factor and with r(C) = 2. Let n satisfy 6 ≤ n ≤ m. Then

H(n; C) = 0 ∗ H(n − 1; C_{0}) ⋃ 1 ∗ H(n − 1; C_{1}),

r(C_{0}) = m > 2, and r(C_{1}) = 1. Inductively, there is a Gray code L_{0} for H(n − 1; C_{0}) containing the path [V_{n−1}, W_{n−1}, Y_{n−1}] = [101^{n−3}, 1^{n−1}, 01^{n−2}], and a Gray code L_{1} for H(n − 1; C_{1}) containing the path [V_{n−1}, W_{n−1}, X_{n−1}] = [101^{n−3}, 1^{n−1}, 110^{n−4}]. A Gray code L for H(n; C) can be formed by joining 0 ∗ L_{0} and 1 ∗ L_{1} using the path [V_{n−1}, W_{n−1}]. The resulting Gray code L contains the path [01^{n−1}, 1^{n}, 11101^{n−4}] = [Y_{n}, W_{n}, Z_{n}]. If both L_{0} and L_{1} are cyclic, then L is cyclic. Otherwise, |h^{∗}(n − 1; C ∗ a_{m−n})| = 1 and h^{∗}(n − 1; C ∗ \overline{a}_{m−n}) = 0 by Corollary 4.1. Thus, L_{\overline{a}_{m−n}} is cyclic, and L_{a_{m−n}} is between S_{n−1} and T_{n−1}. The resulting L is between S_{n} and T_{n}.

Inductive step for Part 3. Let C ∈ Σ_{2}^{∗} be a string with no A-factor and with r(C) > 2. Let n satisfy 5 ≤ n ≤ m. First consider when r(C) = 3 and n > 6 (n = 5, 6 were examined in the basis). Let C_{00} = C ∗ 00, and similarly define C_{01}, C_{10}, and C_{11}. Since m ≥ n > 6, we know r(C_{01}) = 1, and r(C_{ij}) > 2 for ij ≠ 01. There exist Gray codes L_{ij} for H(n − 2; C_{ij}), where L_{01} contains the path [V_{n−2}, W_{n−2}, X_{n−2}] = [101^{n−4}, 1^{n−2}, 1101^{n−5}], and, for ij ≠ 01, L_{ij} contains the path [V_{n−2}, W_{n−2}, Y_{n−2}] = [101^{n−4}, 1^{n−2}, 01^{n−3}].

The individual Gray codes can be joined as in Figure A.1. We first form the subpath [01^{n−1}, 1^{n}, 101^{n−2}, 001^{n−2}]. We then use the outer two strings on the specified subpaths of the L_{ij} to finish connecting the L_{ij}. During this process, we must use the paths [011^{n−2}, 011101^{n−5}] and [01101^{n−4}, 11101^{n−4}]. This ensures that the rest of the connections can be made. If h^{∗}(n; C) = 0, then h^{∗}(n − 2; C_{ij}) = 0 for all ij by repeated applications of Corollary 4.1. Thus, all of the L_{ij} are cyclic, and the resulting L is cyclic. By the same corollary, if |h^{∗}(n; C)| = 1, then |h^{∗}(n − 2; C_{xy})| = 1, where xy = a_{m−n}a_{m−n+1}, and h^{∗}(n − 2; C_{ij}) = 0 for ij ≠ xy. Then L_{xy} is between S_{n−2} and T_{n−2}, and L_{ij} is cyclic for ij ≠ xy. In this case, L starts and ends on the correct

[figure: 101^{n−4}; 1^{n−2}; 1101^{n−5}; 101^{n−4}; 1^{n−2}; 01^{n−3}; 101^{n−4}; 1^{n−2}; 01^{n−3}; 101^{n−4}; 1^{n−2}; 01^{n−3}; L_{00}; L_{10}; L_{11}; L_{01}]

Figure 7: Constructing Gray code when r(C) = 3

strings. In Figure A.1, we illustrate the construction when xy = 01. We include paths for both cyclic and non-cyclic L_{xy}.

Finally, consider when r(C) ≥ 4 and 5 ≤ n ≤ m. Then r(C_{0}) ≥ 3 and r(C_{1}) ≥ 3. There exist Gray codes L_{0} and L_{1} for H(n − 1; C_{0}) and H(n − 1; C_{1}), respectively. Each L_{i} contains the path [V_{n−1}, W_{n−1}, Y_{n−1}] = [101^{n−3}, 1^{n−1}, 01^{n−2}]. Join the L_{i} using the path [V_{n−1}, W_{n−1}]. This forms a Gray code L for H(n; C) containing the path [V_{n}, W_{n}, Y_{n}]. If both L_{i} are cyclic, then L is cyclic. Otherwise, as in the other cases, L is between the specified endpoints.

This completes the proof of the lemma. □

We can then obtain the following corollary of Lemma A.1.

Corollary A.1 Fix q = 2, m ≥ 4 even, and let A be the periodic string of length m with minimal base 10. For any n, 1 ≤ n ≤ m, and for any C ∈ Σ_{2}^{∗} with no Afactor, there is a Gray code for H(n; C). When h^{∗}(n; C) = 0, the Gray code is cyclic. Otherwise, its endpoints are independent of C and of equal parity.

Proof. Most of the Gray codes are supplied by Lemma A.1. The possibilities not covered by Lemma A.1 are when r(C) = 1 and n ≤ 4, or when r(C) > 1 and n ≤ 3. In the former case, H(n; C) = 1 ∗ H(n − 1; C_{1}), and r(C_{1}) = m − 1 ≥ 3. So H(n; C) = 1 ∗ Σ_{2}^{n−1} if either m > 4 or n < 4, and H(n; C) = 1 ∗ (Σ_{2}^{3} \{010}) if n = m = 4. There certainly exist Gray codes in these cases. In the latter case, if r(C) > n, then H(n; C) = Σ_{2}^{n}. If r(C) = k ≤ n, then

H(n; C) = {D ∈ Σ_{2}^{n}|D does not begin with a_{m−k} … a_{m−1}}.

Again, Gray codes are easy to find. □

A.2 Gray codes when n > m

In this section, we prove the following results. These results are analogs to Lemma 4.5 and Theorem 4.4 of Section 4.

Lemma A.2 Fix q = 2, m ≥ 4 even, and let A be the periodic string of length m with minimal base 10. For all C with no A-factor and all n, m + 1 ≤ n ≤ m + 2, there exist a Gray code for H(n; C). When h^{∗}(n; C) = 0, the Gray code is cyclic, and when |h^{∗}(n; C)| = 1, the Gray code is between two strings independent of C and of equal parity.

Theorem A.1 Fix q = 2, m ≥ 4 even, and let A be the periodic string of length m with minimal base 10. For n ≥ 1, there exists a Gray code for F(n). When f^{∗}(n) = 0, there exists a cyclic Gray code.

We first prove Lemma A.2. We prove only the n = m + 1 case, the n = m + 2 proof being similar. Let C ∈ Σ_{2}^{∗} be a string with no A-factor. By Lemma 4.2, h^{∗}(m; C) = 0 if and only if C ends in 10. Otherwise, |h^{∗}(m; C)| = 1. Since C_{1} cannot end in 10, |h^{∗}(m; C_{1})| = 1. Likewise, h^{∗}(m; C_{0}) = 0 iff C ends in 1.

By Corollary A.1, there exist strings S′, T′ ∈ Σ_{2}^{m}, of equal parity, such that for any D with no A-factor and not ending in 10, there is a Gray code for H(m; D) between S′ and T′. When |h^{∗}(m + 1; C)| = 1, we prove there is a Gray code for H(m + 1; C) between S = 1 ∗ S′ and T = 1 ∗ T′.

First suppose r(C) = 1. By Corollary A.1, there is a Gray code L_{1} for H(m; C_{1}) between S′ and T′. Then L = 1 ∗ L_{1} is a Gray code for H(m + 1; C) satisfying the conditions of the lemma.

Next suppose r(C) = 2, so r(C_{0}) > 2 and r(C_{1}) = 1. In this case, C ends in 10, so |h^{∗}(m; C_{0})| = 1 and |h^{∗}(m; C_{1})| = 1. By Corollary A.1, for i = 0, 1, there exists a Gray code L_{i} for H(n; C_{i}) between S′ and T′. Then 0 ∗ L_{0}, 1 ∗ L_{1} is a cyclic Gray code for H(m + 1; C).

Finally, suppose r(C) > 2 so r(C_{i}) > 1 for i = 0, 1. By Lemma A.1, there exist strings W_{m} and Y_{m} such that, for i = 0, 1, there exists a Gray code L_{i} for H(m; C_{i}) containing the path [W_{m}, Y_{m}]. Since C_{1} does not end in 10, |h^{∗}(m; C_{1})| = 1 and L_{1} runs between S′ and T′. The Gray code L_{0} can either be cyclic (when C ends in 1) or between S′ and T′ (when C ends in 0 or C = ϵ). If L_{0} is between S′ and T′, then 0 ∗ L_{0}, 1 ∗ L_{1} is a cyclic Gray code for H(m + 1; C). If L_{0} is cyclic, then 0 ∗ L_{0} can be spliced into 1 ∗ L_{1} using the path [W_{m}, Y_{m}]. In either case, the resulting Gray code satisfies the restrictions of the lemma.

This completes the construction of the Gray code for H(m + 1; C). A similar case by case analysis can be performed when n = m + 2. This finishes the proof of Lemma A.2.

We now prove Theorem A.1. As in Section 4.5, we use Lemma 4.1 to prove this theorem. Let C ∈ Σ_{2}^{∗} be any string with no A-factor. Corollary A.1 and Lemma A.2 provide Gray codes for H(n; C) when 1 ≤ n ≤ m + 2. They provide cyclic Gray codes whenever h^{∗}(n; C) = 0. Lemma 4.6 proves that |h^{∗}(m + 2; C)| = 1 for any C with no A-factor, thus yielding Gray codes for H(m + 2; C) between two strings independent of C and of equal parity. We can then apply Lemma 4.1 to conclude that, for all n ≥ 1 and for all C with no A-factor, there exists a Gray code for H(n; C). When h^{∗}(n; C) = 0, there is a cyclic Gray code.

In this appendix, we have constructed Gray codes for H(n; C) when A is periodic with minimal base 10. This, in essence, completes the proof of Theorem 4.4 in Section 4 which stated that if A is periodic with a t.a. minimal base, then there exists a Gray code for F(n) for all n ≥ 1.