APPENDIX A

Some Interesting Star-Free Identities

In the course of this work many properties of star-free expressions were studied and some interesting properties not relevant to the main body of work were encountered. They have been included here.

Sometimes it is useful to manipulate the complement of an expression instead of the expression itself. Consider the following example:

R=(λ+0)'(λ+1)'
=(1+IA²)(0+IA²)	(i)
=10+IA²0+1IA²+IA²IA²	(ii)
=10+IA²0+1IA²+IA⁴	(iii)
=10+A²0+1A²+IA⁴	(iv)
hence R'=λ+0+1+00+01+11+001+011	(v)
=(λ+0)(λ+0+1)(λ+1)	(vi)
hence (λ+0)'(λ+1)'=((λ+0)(λ+0+1)(λ+1))'	(vii)

For completeness the steps taken above are explained:

Taking words of length zero, there is one, λ and it is contained in λ+0, hence not in (λ+0)'. Taking words of length one, there are 0 and 1; only 0 is contained in λ+0, therefore 1 must be contained in (λ+0)'. There are no words of length two or greater in λ+0; hence all of these must be contained in (λ+0)'. A² represents all words of length 2, while IA² represents all words of length 2 or greater. Hence (λ+0)'=(1+IA²).
This step is simply a multiplication, keeping in mind that our multiplication (concatenation) is not commutative.
All words of length two or more followed by all words of length two or more is obviously just all words of length four or more. Alternatively, it can be shown that I and A² commute and that II=I, hence IA²IA²=IA⁴.
IA²0 is all words of length two or more followed by 0 or all words of length three or more ending in 0. All words of length four or more are already contained in IA⁴ hence IA²0+IA⁴=A²0+IA⁴.
(A²0+1A²) contains all words of length three ending in 0 or starting with 1. Hence (A²0+1A²)' contains all words starting with 0 and ending in 1, namely 0A1=001+011.
This step is merely a factoring.

This has been merely an example of the technique. Now we will turn to some generalizations. Consider the expressions:

R=(λ+X₁)'(λ+X₂)' where X₁, X₂ ⊆A
hence R=(A-X₁+IA²)(A-X₂+IA²)
=(A-X₁)(A-X₂)+(A-X₁)IA²+IA²(A-X₂)+IA⁴
=(A-X₁)(A-X₂)+(A-X₁)A²+A²(A-X₂)+IA⁴
hence R'=λ+A+X₁A+AX₂+X₁AX₂
=(λ+X₁)(λ+A)(λ+X₂)
hence (λ+X₁)'(λ+X₂)'=((λ+X₁)(λ+A)(λ+X₂))'

If we set A=0,1, X₁=0, X₁=1 we have

(λ+0)'(λ+1)'=((λ+0)(λ+0+1)(λ+1))'

which was the result found in the first example. We may generalize this further. Consider:

P=(λ+A+A²+...+A^k-1+X₁)'(λ+A+A²+...A^l-1+X₂)'
where X₁⊆A^k,X₂⊆A^l
P=((A^k-X₁)+IA^k+1)((A^l-X₂)+IA^l+1)
=(A^k-X₁)(A^l-X₂) [length k+l]
+(A^k-X₁)A^l+1+A^k+1(A^l-X₂) [length k+l+1]
+IA^k+l+2 [length k+l+2]
hence P'=Σ_i=0^k+l-1Aⁱ+X₁A^l+A^kX₂+X₁AX₂
=(λ+A+A²+ ... +A^k-1+X₁)(λ+A)(λ+A+A²+ ... +A^l-1+X₂
hence (λ+A+A²+ ... +A^k-1+X₁)'(λ+A+A²+ ... +A^l-1+X₂)'
=((λ+A+A²+ ... +A^k-1+X₁)(λ+A)(λ+A+A²+ ... +A^l-1+X₂))'

Consider also:

P=(X₁)'(λ+X₂)'(λ+X₃)'...(λ+X_n)' where X_i⊆A for i=1,n.
P=(λ+A-X₁+IA²)(A-X₂+IA²)(λ+X₃)'...(λ+X_n)'
=(λ+X₂)'(λ+X₃)' ... (λ+X_n)'

Hence terms not including λ are absorbed in the presence of terms including λ.

Consider now an expression of terms all without λ:

P=(X₁)'(X₂)'...(X_n)' where X_i⊆A for i=1 to n
=(λ+A-X₁+IA²)(λ+A-X₂+IA²)...(λ+A-X_n+IA²)
=λ+A-X₁+A-X₂...+A-X_n+IA²
hence P'=X₁∩X₂∩...∩X_n hence P=(X₁∩X₂∩...∩X_n)'

Hence all terms not including λ can be reduced to one term not containing λ but containing the intersection of the contents of the original terms. So far we have shown the following:

(λ+X₁)'(λ+X₂)'=((λ+X₁)(λ+A)(λ+X₂))'
(X₁)'(X₂)'...(X_n)'=(X₁∩X₂∩...∩X_n)'
(X₁)'(λ+X₂)'(λ+X₃)'...(λ+X_n)'=(λ+X₂)'(λ+X₃)'...(λ+X_n)'
for any X_i⊆A for any A

Also:

(λ+A+A²+...+A^k-1+X_k)'(λ+A+A²+...A^l-1+X_l)'
=((λ+A+A²+...+A^k-1+X_k)(λ+A)(λ+A+A²+...A^l-1+X_l))'
for any X_k⊆A^k, X_l⊆A^l for any A

We can also show the following:

(λ+X₁)'(λ+X₂)'(λ+X₃)'=((λ+X₁)(λ+A)(λ+X₂)(λ+A)(λ+X₃))'
((λ+X₁)(λ+X₂))'((λ+X₃)(λ+X₄))'=((λ+X₁)(λ+X₂)(λ+A)(λ+X₃)(λ+X₄))'

A logical extension would be:

(λ+X₁)'(λ+X₂)'...(λ+X_n)'
=((λ+X₁)(λ+A)(λ+X₂)(λ+A)...(λ+A)(λ+X_n))'

and a proof has been attempted but appears elusive. An attempt follows:

P=(λ+X₁)'(λ+X₂)'...(λ+X_n)'
=(A-X₁+IA²)(A-X₂+IA²)...(A-X_n+IA²)
=IA²ⁿ [length 2n]
+(A-X₁)A^2n-2+A²((A-X₂+IA²)A^2n-4+...+A^2n-2(A-X_n) [length 2n-1]
+(A-X₁)(A-X₂)A^2n-2+... +A^2p-2(A-X_p)A^2q-2p-2(A-X_q)A^2n-2q+... +A^2n-4(A-X_n-1)(A-X_n) [length 2n-2]
+A²(A-X₂)...(A-X_n) +(A-X₂)...(A-X_p)A²(A-X_p+2)...(A-X_n) +... +(A-X₁)...(A-X_n-1)A² [length n+1]
+(A-X₁)(A-X₂)...(A-X_n) [length n]

Note: There are no terms of length <n. All terms of length ≥2n are included. Also the I's may be removed from lines of length 2n-1 to n+1 because the words represented in each case with the I's included are included in the line above.

Q=((λ+X₁)(λ+A)(λ+X₂)(λ+A)...(λ+A)(λ+X_n))'
Q'=(λ+X₁)(λ+A)(λ+X₂)(λ+A)...(λ+A)(λ+X_n)
=λ+A+A²+...+A^n-1 [length <n]
+X₁A^n-1+AX₂A^n-2+...+A^r-1X_rA^n-r+...A^n-1X_n [length n]
+X₁AX₂A^n-2+...+A^p-1X_pA^q-pX_qA^n-q+...+A^n-2X_n-1AX_n [length n+1]
+AX₂AX₃A...AX_n+X₁AAX₃A...AX_n+...X₁AX₂A...AX_n-1A [length 2n-2]
+X₁AX₂A...AX_n [length 2n-1]

Note: All terms of length <n are present. No terms of length ≥2n are present.

Comparing P and Q':

terms of length <n are in Q' and not in P.
terms of length ≥2n are in P and not in Q'. Hence we need only consider terms of length m such that n≤m<2n.
Consider terms of length 2n-1:
P contains all such terms whose first letter is not in X₁, or whose third letter is not in X₂, ... or whose last letter is not in X_n. Hence the only words of length 2n-1 remaining outside of P are exactly those words whose first letter is in X₁ and whose third letter is in X₂ ... and whose last letter is in X_n, that is X₁AX₂AX₃A...AX_n and this is exactly the term contained in Q'. Hence the terms of length 2n-1 in P and Q' are complementary.
Consider terms of length 2n-2:
For every term t_pq in P with A-X_p in position 2p-1 and A-Xq in position 2q-2, each term in Q' has either Xp in postion 2p-1 or X_q in position 2q-2 or both. Hence any t_pq in P is not in Q'. For every term t_s in Q' missing X_s, P has all X_p such that p<s in position 2p-1, and all X_q such that q>s in position 2q-2. Hence any t_s in Q' is not in P. It is thus apparent that terms of length 2n-2 are complementary in P and Q'.
Similarly, it can be shown that terms of length 2n-3 to n+1 are complementary.
Consider terms of length n:
Q' contains all terms whose first letter is in X₁ or whose second letter is in X₂, etc. The only words of length n remaining are those whose first letter is not in X₁ and whose second letter is not in X₂, etc., which is exactly the term of length n in P. Hence the words of length n in P and Q' are complementary.

Hence P=Q.

A rigorous proof of this relationship and further relationships are left as work for future study.