Primitivity, Uniform Minimality, and State
Complexity of Boolean Operations

arXiv:1702.00877v3 [cs.FL] 26 Mar 2018

Sylvie Davies
University of Waterloo
Department of Pure Mathematics
sldavies@uwaterloo.ca

Abstract. A minimal deterministic finite automaton (DFA) is uniformly
minimal if it always remains minimal when the final state set is replaced
by a non-empty proper subset of the state set. We prove that a permutation DFA is uniformly minimal if and only if its transition monoid is a
primitive group. We use this to study boolean operations on group languages, which are recognized by direct products of permutation DFAs.
A direct product cannot be uniformly minimal, except in the trivial case
where one of the DFAs in the product is a one-state DFA. However, nontrivial direct products can satisfy a weaker condition we call uniform
boolean minimality, where only final state sets used to recognize boolean
operations are considered. We give sufficient conditions for a direct product of two DFAs to be uniformly boolean minimal, which in turn gives
sufficient conditions for pairs of group languages to have maximal state
complexity under all binary boolean operations (“maximal boolean complexity”). In the case of permutation DFAs with one final state, we give
necessary and sufficient conditions for pairs of group languages to have
maximal boolean complexity. Our results demonstrate a connection between primitive groups and automata with strong minimality properties.

1

Introduction

Formal definitions are postponed until later.
The state complexity of a regular language is the minimal number of states
needed to recognize the language with a deterministic finite automaton. It is
well-known that if Lm and L′n are regular languages over a common alphabet
Σ with state complexity m and n respectively, then the state complexity of
Lm ∪ L′n is at most mn, and this bound is tight for all m, n ≥ 2. The upper
bound follows from the standard “direct product” automaton construction for
recognizing unions of regular languages. Examples which meet the bound were
given by Maslov in 1970 [15], and independently by Yu, Zhuang and Salomaa in
1994 [21], who noted that the same bound holds for intersection.
More generally, if ◦ is a binary boolean operation on languages over Σ, then
Lm ◦L′n has state complexity at most mn, and this bound is tight for all m, n ≥ 2
if and only if ◦ is proper, that is, not a constant function (L◦L′ = ∅ or L◦L′ = Σ ∗ )
or a function that depends on only one argument (for example, L ◦ L′ = Σ ∗ \ L).

This was proved by Brzozowski in 2009 [5], who gave examples showing that mn
is a tight bound for symmetric difference, and noted that the examples for union
and symmetric difference (together with their complements) suffice to prove mn
is a tight upper bound for all proper binary boolean operations.
To prove a lower bound on the worst-case state complexity of a regular operation, it suffices to give just one family of examples that meet the bound. Such
families are called witnesses. Witnesses are known for most commonly used unary
and binary operations on regular languages. However, there are several directions
of research in state complexity which necessitate finding new witnesses for operations that have previously been studied. For example, sometimes the first
witnesses found for an operation are not optimal in terms of alphabet size, so
researchers will look for new witnesses over a smaller alphabet. When studying
the n-ary versions of binary operations, such as the union of n languages, or
more generally combined operations [13,18], such as the star of a union of languages, again new witnesses are needed. It is also interesting to consider families
of languages that are simultaneous witnesses for multiple operations; it is not
generally the case that a witness for one operation will work for others. Brzozowski found a family of languages which is a simultaneous witness for reversal,
star, concatenation and all binary boolean operations [6]. Each of the problems
just mentioned, as well as the fundamental problem of determining the worstcase state complexity of an operation, may also be studied in subclasses of the
regular languages, such as the star-free languages [9] or ideal languages [8]. Often
the known witnesses do not lie in the subclass, so new witnesses must be found.
In some cases, new witnesses can be found by making slight modifications to
known witnesses, but this is not always successful. Furthermore, this technique
does little to advance our understanding of why particular witnesses work. For
these reasons, it is desirable to have results which describe the general landscape
of witnesses for a particular operation. By this we mean results that give necessary conditions for witnesses, revealing common structural properties that all
witnesses share, or sufficient conditions allowing one to easily generate examples of witnesses or check whether a candidate family is a witness. For example,
Salomaa, Wood and Yu proved that a regular language of state complexity n is
a witness for the reversal operation if the transition monoid of its minimal DFA
has the maximal possible size nn [19]; this gives a general sufficient condition
for a language to be a witness for reversal. Ideally, collecting results of this sort
would eventually lead to a complete classification of witnesses for commonly
used operations. In reality, we suspect the problem of fully classifying witnesses
is only tractable in very special cases, but even results which take small steps in
this direction can be quite useful and enlightening.
The main inspiration for this work is a paper of Bell, Brzozowski, Moreira,
and Reis [3], which considers the following question: for which pairs of languages
(Lm , L′n ) (with state complexities m and n respectively) does Lm ◦ L′n reach
the maximal state complexity mn for every proper binary boolean operation
◦? Bell et al. give sufficient conditions for this to occur. The conditions are
based on the transition monoids of the minimal deterministic automata of Lm
2

and L′n ; essentially, if the transition monoids contain the symmetric groups Sm
and Sn , then “usually” (i.e., excluding a known class of counterexamples) the
language Lm ◦ L′n will have state complexity mn. We obtain a refinement of this
result: we prove that if the transition monoids contain 2-transitive groups, then
“usually” Lm ◦ L′n has state complexity mn (though our notion of “usually” is
more restrictive than that of Bell et al.).
We also obtain necessary and sufficient conditions for Lm ◦ L′n to have state
complexity mn in the special case where the minimal automata for Lm and L′n
have exactly one final state, and their transition monoids contain a transitive
permutation group. We can view this result as solving a particular special case
of the problem of characterizing witnesses for boolean operations.
To obtain these results, we exploit a connection between a certain class of
permutation groups called primitive groups, and the notion of uniformly minimal automata introduced by Restivo and Vaglica [16]. A minimal deterministic
finite automaton (DFA) is uniformly minimal if it always remains minimal when
the final state set is replaced by a non-empty proper subset of the state set. For
a permutation DFA (that is, a DFA whose transition monoid is a permutation
group), uniform minimality is equivalent to primitivity of the transition monoid.
Although uniform minimality played an important role in the paper of Bell et
al., this connection with primitive groups was not used in their paper. Primitive
groups are an important and well-studied class of permutation groups; there are
deep results on their structure, and large libraries of primitive groups are available in computer algebra systems such as GAP [14] and Magma [4]. Uniformly
minimal DFAs have received comparatively little study; thus this connection has
significant implications for the theory of uniformly minimal DFAs.
The paper is structured as follows. Section 2 contains background material
needed to understand the paper. Section 3 discusses the relationship between
primitive groups and uniformly minimal permutation DFAs. Section 4 contains
our main results on witnesses for the maximal state complexity of boolean operations. Section 5 concludes the paper by giving a summary of our results and
stating some open problems.

2

Definitions and Notation

For a function f : X → Y , we typically write the symbol f to the right of
its arguments. For example, if the image of x under f is y, we write xf =
y. Functions are composed from left to right, and composition is denoted by
juxtaposition: if g : Y → Z, then f g denotes the composition of f and g, and
x(f g) = (xf )g = yg is an element of Z.
Let P(X) denote the power set of X, that is, the set of all subsets of X. Given
f : X → Y we may extend f by union to obtain a function f : P(X) → Ye (where
S
Ye is the closure of Y under union) defined by Sf = x∈S xf for S ⊆ X. We
denote the extension by the same symbol as the original function. Note that for
convenience, we often make no distinction between an element of a set and the
singleton containing the element; so x∪x′ = {x}∪{x′ } = {x, x′ } and xf = {x}f .
3

2.1

Monoids, Groups and Actions

A monoid is a set M equipped with an associative binary operation · and an
identity element e such that m · e = e · m = m for all m ∈ M . Typically we
omit the symbol for the operation; so the previous equation could be written as
me = em = m. For n ≥ 1 we write mn for the n-fold product of m with itself,
and define m0 = e for all m ∈ M . If for each m ∈ M , there exists m′ ∈ M such
that mm′ = m′ m = e, then M is called a group, and m′ is called the inverse of
M and denoted m−1 . The order of an element g of a group is the least integer
n ≥ 1 such that g n = e.
A submonoid of M is a subset M ′ ⊆ M which is closed under · and contains
the identity e of M . If additionally M ′ is a group, it is called a subgroup of M ;
we write M ′ ≤ M to mean that M ′ is a subgroup of M . Note that we do not
allow submonoids or subgroups of M to have an identity element different from
that of M . If x1 , . . . , xk are elements of a group G, then hx1 , . . . , xk i denotes the
group generated by x1 , . . . , xk , the smallest subgroup of G containing x1 , . . . , xk .
Let M and M ′ be monoids with identity elements e and e′ respectively. A
homomorphism from M to M ′ is a function ϕ : M → M ′ such that (m1 m2 )ϕ =
(m1 )ϕ(m2 )ϕ for all m1 , m2 ∈ M and eϕ = e′ . A bijective homomorphism is
called an isomorphism, and two monoids are said to be isomorphic if there exists
an isomorphism from one to the other. We write M ∼
= M ′ to mean that M and
′
′
M are isomorphic. If G and G are groups and ϕ : G → G′ is a homomorphism,
the kernel of ϕ is the set ker ϕ = {g ∈ G : gϕ = e′ }, that is, the set of elements of
G that map to the identity of G′ . If G is a group, N ≤ G, and gng −1 ∈ N for all
g ∈ G and n ∈ N , we say N is a normal subgroup of G. A group G is simple if it
has no non-trivial proper normal subgroups, that is, the only normal subgroups
of G are G itself and the trivial group (containing just the identity element of
G). The kernel of a homomorphism from G to another group is always a normal
subgroup of G. We occasionally use the following elementary facts about normal
subgroups and homomorphisms:
– If ϕ : G → G′ is a homomorphism and ker ϕ is the trivial one-element subgroup of G, then ϕ is injective.
– If ϕ : G → G′ is a surjective homomorphism and N is a normal subgroup of
G, then N ϕ is a normal subgroup of G′ .
A monoid action of M on a set X is a function ψ : X × M → X such
that ((x, m)ψ, m′ )ψ = (x, mm′ )ψ and (x, e)ψ = x for all m, m′ ∈ M and x ∈ X.
Equivalently, it is a family of functions mψ : X → X such that mψ m′ψ = (mm′ )ψ
for all m, m′ ∈ M and eψ is the identity map on X. The map mψ is called the
action of m. To simplify the notation, we often omit the action symbol ψ and just
write xm instead of xmψ or (x, m)ψ. Furthermore, we typically avoid assigning
a symbol to the action at all; rather than “let ψ be a monoid action of M on X”
we write “let M be a monoid acting on X”, meaning that M has a specific but
nameless action on X associated with it. If S ⊆ M generates the monoid M , a
monoid action ψ is completely determined by its values on elements of S. If M
is a group, we use the term group action rather than monoid action.
4

Let G be a group acting on X. For x ∈ X, the stabilizer subgroup or simply
stabilizer of x is the subgroup {g ∈ G : xg = x} of G. For S ⊆ X, the setwise
stabilizer of S is the subgroup {g ∈ G : Sg = S}. Elements of the setwise
stabilizer need not fix every element of S; for example, if 1g = 2 and 2g = 1
then g is in the setwise stabilizer of {1, 2}.
Let X be a finite set. A function t : X → X is called a transformation of X.
The set of all transformations of X is a monoid under composition called the
full transformation monoid TX . A submonoid of TX is called a transformation
monoid on X. The degree of a transformation monoid on X is the size of X.
If M is a transformation monoid on X, the monoid action ψ : X × M → X
given by (x, t)ψ = xt for x ∈ X, t ∈ M is called the natural action of M . If
X = {1, . . . , n} we write Tn for TX .
A bijective transformation of X is called a permutation of X. We can describe
any particular permutation of X using cycle notation as follows. For x1 , . . . , xk ∈
X, we write (x1 , . . . , xk ) for the permutation that sends xi to xi+1 for 1 ≤ i < k,
sends xk to x1 , and fixes all other elements of X. This permutation is called
a cycle of length k, or simply a k-cycle. All permutations that are not cycles
can be expressed as a product of cycles. The identity permutation is denoted
by an empty cycle, i.e., “()”. Cycle notation conflicts with the notation we use
for ordered k-tuples, but this should not cause confusion. We mainly use cycle
notation when giving concrete examples of permutations.
The set of all permutations of X is a subgroup of TX called the symmetric
group SX . A subgroup of SX is called a permutation group on X; this a special
type of transformation monoid and we have the same notions of degree and
natural action. The alternating group AX is the subgroup of SX consisting of all
permutations that can be expressed as a product of an even number of 2-cycles.
If X = {1, . . . , n} we write Sn for SX and An for AX .
Let G be a group acting on X. We say that the action of G is transitive or
that G acts transitively on X if for all x, x′ ∈ X, there exists g ∈ G such that
xg = x′ . We say the action of G is k-transitive or G acts k-transitively on X if
for all pairs of k-tuples (x1 , . . . , xk ), (x′1 , . . . , x′k ) ∈ X k , there exists g ∈ G such
that for 1 ≤ i ≤ k we have xi g = x′i ; informally, k-transitive means “transitive
on k-tuples”.
A non-empty set B ⊆ X is called a block for G if for all g ∈ G, either
Bg ∩ B = B (equivalently, Bg = B) or Bg ∩ B = ∅. A block B is trivial if it is a
singleton or the entire set X. We say the action of G is primitive or that G acts
primitively on X if it is transitive and all of its blocks are trivial. Equivalently,
a transitive group action of G is primitive if for every set S ( X with at least
two elements, there exists g ∈ G such that ∅ ( Sg ∩ S ( S.
If G is a permutation group and the natural action of G is transitive (ktransitive, primitive), then we say G is a transitive group (k-transitive group,
primitive group). For example, the cyclic group h(1, 2, 3, 4)i ≤ S4 is a transitive
group, since its natural action on {1, 2, 3, 4} is transitive. This terminology can
cause confusion, since transitivity, k-transitivity and primitivity are properties
of actions and not groups; statements like “G is transitive” or “G is primitive”
5

are statements about a particular action of G (the natural action) rather than
the abstract group itself. In particular, these properties are not preserved under
isomorphism; for example, the group h(5, 6, 7, 8)i ≤ S8 is not transitive, but it is
isomorphic to the transitive group h(1, 2, 3, 4)i ≤ S4 .
As the notions of transitivity and primitivity are central to this paper, we
give numerous examples to illustrate them below.
Example 1. Consider the group G = h(1, 2, 3, 4, 5, 6)i ≤ S6 . This group is clearly
transitive, since its natural action on {1, 2, 3, 4, 5, 6} is transitive. However, it is
imprimitive, since {1, 3, 5} and {2, 4, 6} are non-trivial blocks. Indeed, if we let
a = (1, 2, 3, 4, 5, 6), then {1, 3, 5}a = {2, 4, 6} and {2, 4, 6}a = {3, 5, 1}. Hence
for all k ≥ 0, we either have {1, 3, 5}ak ∩ {1, 3, 5} = ∅ or {1, 3, 5}ak ∩ {1, 3, 5} =
{1, 3, 5}, and similarly for {2, 4, 6}. One may also verify that {1, 4}, {2, 5} and
{3, 6} are non-trivial blocks, and that there are no blocks of size 4 or 5.

Example 2. Consider the group G = h(1, 2, 3, 4, 5)i ≤ S5 . This group is clearly
transitive, and it is also primitive. To see this, suppose for a contradiction that B
is a non-trivial block. Let a = (1, 2, 3, 4, 5) and let k = |b − b′ |, where b and b′ are
distinct elements of B. Then Bak ∩ B 6= ∅, so we must have Bak = B since B is
a block. Thus for each i ∈ B, we have iak ∈ Bak , and thus iak ∈ B. Then since
iak ∈ B, we have ia2k ∈ Bak , and thus ia2k ∈ B. By induction it follows that
{iank : n ≥ 0} ⊆ B. We claim {iank : n ≥ 0} = {1, 2, 3, 4, 5}, which contradicts
the fact that B is a non-trivial block. Indeed, for j ∈ {1, 2, 3, 4, 5}, we have
iank = j if and only if i + nk ≡ j (mod 5). Since 5 is prime and 0 < k < 5, we
see that k is coprime with 5. Hence by elementary number theory, there exists n
such that nk ≡ j − i (mod 5) and so i + nk ≡ i + j − i ≡ j (mod 5) as required.
Hence j ∈ {iank : n ≥ 0} for all j ∈ {1, 2, 3, 4, 5}, which proves the claim. It
follows G has no non-trivial blocks, and thus G is primitive.

The above argument can be generalized to prove that a cyclic group G =
h(1, 2, . . . , n)i is primitive if and only if n is prime. If a = (1, 2, . . . , n), then for
each divisor d of n and each integer 1 ≤ i ≤ n, we see that {iamd : m ≥ 0} is a
block. In particular, when n is composite, there exists a divisor d with 1 < d < n,
giving rise to a non-trivial block.
Example 3. Consider the group G = h(1, 2, 3), (4, 5, 6)i ≤ S6 . This group is intransitive, since (for example) it does not contain a permutation mapping 1 to
4. Thus it is imprimitive by definition. Alternatively, observe that {1, 2, 3} and
{4, 5, 6} are non-trivial blocks for G.
Generally an intransitive group will always have non-trivial blocks, but there
is one exception: the trivial subgroup of S2 (containing only the identity element). The natural action of this group is clearly not transitive on {1, 2}, but
its only blocks are the trivial blocks {1}, {2} and {1, 2}. To avoid dealing with
this exception, we require primitive groups to be transitive by definition.

The next example shows that we have the following hierarchy of permutation
group properties:
(2-transitive) ⇒ (primitive) ⇒ (transitive).
6

These implications do not reverse. Cyclic groups of composite order give examples of transitive imprimitive groups, while cyclic groups of prime order p ≥ 5
give examples of primitive, non-2-transitive groups. (For example, the group
h(1, 2, 3, 4, 5)i ≤ S5 is not 2-transitive on {1, 2, 3, 4, 5} since nothing maps the
pair (1, 2) to the pair (1, 3).)
Example 4. The alternating group An is 2-transitive for n ≥ 4. Indeed, given
i, i′ , j, j ′ ∈ {1, . . . , n}, the permutation (i, i′ )(j, j ′ ) is the product of an even
number of 2-cycles, and it maps the pair (i, j) to (i′ , j ′ ). We claim An is also
primitive for n ≥ 2. To see this, first note that An is a cyclic group of prime order
for 2 ≤ n ≤ 3. For n ≥ 4, suppose for a contradiction that B is a non-trivial
block. Then B has at least two elements i and j, but B is not all of {1, . . . , n}.
Choose k ∈ {1, . . . , n} \ B. Since An is 2-transitive, there exists an element
g ∈ An which maps the pair (i, j) to (j, k). Then Bg ∩ B 6= ∅ (since Bg and B
contain j), and thus Bg ∩ B = Bg = B since B is a block. But Bg contains k
and B does not, which is a contradiction. Thus all blocks of An are trivial, and
thus An is primitive. In fact, this argument shows that all 2-transitive groups
are primitive.

The following fact is immediate from the definitions of transitivity and primitivity, and is frequently useful: if H is a subgroup of G and H is transitive
(primitive), then G is also transitive (primitive). For example, the symmetric
group Sn is primitive for n ≥ 2, since it contains the primitive group An .
So far, we have only looked at cyclic groups and the symmetric and alternating groups. For our last pair of examples, we consider two subgroups of S6 that
are a little more interesting.
Example 5. Define a = (2, 4, 6), b = (1, 5)(2, 4) and c = (1, 4, 5, 2)(3, 6), and let
G = ha, b, ci. We claim this group is transitive on {1, . . . , 6}. For g ∈ G and
g
i, j ∈ {1, . . . , 6}, we will write i −→ j to mean ig = j. Observe that
c3

a2

c

c

1 −→ 2 −→ 6 −→ 3,

c

1 −→ 4 −→ 5.

Thus for each i 6= 1, there is some group element that maps 1 to i. If g ∈ G
maps 1 to i, then g −1 maps i to 1. It follows for each i, j, there is some element
x that maps i to 1, and another element y that maps 1 to j, giving
y

x

i −→ 1 −→ j.
Thus G is transitive. It is also imprimitive, with non-trivial blocks {1, 3, 5} and
{2, 4, 6}. Indeed, we see that
a

b

c

{1, 3, 5} −→ {1, 3, 5}, {1, 3, 5} −→ {5, 3, 1}, {1, 3, 5} −→ {4, 6, 2}.
Hence these sets are non-trivial blocks.



7

Example 6. Define a = (1, 2, 3, 4, 6) and b = (1, 2)(3, 4)(5, 6) and let G = ha, bi.
It is easy to see that this group is transitive on {1, . . . , 6}: just verify that 1
can be mapped to every other element and use the argument from the previous
example. This group is also primitive. To see this, first note that the subgroup hai
acts primitively on {1, 2, 3, 4, 6}, since it is a cyclic group of prime order. Hence
a non-trivial block of G cannot be a subset of {1, 2, 3, 4, 6}, so in particular a
non-trivial block of G must contain 5. Suppose B is a non-trivial block that
contains 5; then Ba ∩ B contains 5 and hence Ba ∩ B = Ba = B. Since B
is non-trivial, it contains some element i 6= 5, and since Ba = B we have
{i, ia, ia2, . . . , ia4 } = {1, 2, 3, 4, 6} ⊆ B. This implies B = {1, 2, 3, 4, 5, 6}, and so
B is trivial, which is a contradiction. Thus all blocks of G are trivial, and thus
G is primitive.

A congruence of a monoid action of M on X is an equivalence relation on
X that is M -invariant in the following sense: if E is an equivalence class, then
for all m ∈ M , there exists an equivalence class E ′ such that Em ⊆ E ′ . In
other words, if x and x′ are equivalent, then xm and x′ m are equivalent for
all m ∈ M . The equality congruence {(x, x) : x ∈ X} in which elements are
equivalent only if they are equal, and the full congruence X × X in which all
elements are equivalent, are called trivial congruences. If M is a transformation
monoid on X, a congruence of the natural action is called an M -congruence.
The notion of congruences leads to an important alternate characterization
of primitivity. In the case of a permutation group G on X, notice that for all
S ⊆ X and g ∈ G, the set Sg has the same size as S. Hence a G-congruence
has the following property: if E is an equivalence class, then for all g ∈ G, the
set Eg is also an equivalence class. In particular, we either have E ∩ Eg = E or
E ∩ Eg = ∅ for all g ∈ G; thus the classes of G-congruences are blocks.
In fact, if G is transitive, then every G-congruence arises from the blocks
of G as follows. If B is a block for G, the block system corresponding to B
is the set {Bg : g ∈ G}. As the name implies, each set in a block system is
also a block for G. Indeed, for all g ′ ∈ G, we either have Bgg ′ ∩ Bg = ∅ or
Bgg ′ ∩ Bg 6= ∅, and in the latter case, Bgg ′ g −1 ∩ B 6= ∅. But B is a block, so this
implies Bgg ′ g −1 = B and thus Bgg ′ = Bg. Thus every set in a block system in
a block, so in particular, all distinct sets in a block system are pairwise disjoint.
Furthermore, since G is transitive, each element of X appears in at least one
block of the system. It follows that block systems are partitions of X, and thus
equivalence relations on X. It is easy to see that block systems are G-invariant,
and thus are G-congruences.
Thus every block gives rise to a block system that is a G-congruence, and every G-congruence consists of blocks; it follows block systems and G-congruences
are one and the same if G is a transitive group. If all G-congruences are trivial,
then all block systems of G consist only of trivial blocks, and vice versa. Thus
we obtain our alternate characterization of primitivity: a transitive permutation
group G on X is primitive if and only if all G-congruences are trivial.
Let us revisit some of our earlier examples of primitive and imprimitive
groups in the context of this new characterization.
8

Example 7. Consider the imprimitive cyclic group G = ha = (1, 2, 3, 4, 5, 6)i ≤
S6 of Example 1. Put an equivalence relation ∼ on X = {1, . . . , 6} by letting
i ∼ j if i and j have the same parity (odd or even). Notice that for i ∈ X, the
elements i and ia have opposite parity. Thus ∼ is a G-congruence, since if i ∼ j
then ia ∼ ja, and so if [i] is the equivalence class of i then [i]a = [ia] is also an
equivalence class. In fact, the classes of ∼ are just the blocks {1, 3, 5} and {2, 4, 6}
we found in Example 1; thus the G-congruence ∼ corresponds to the block system
{{1, 3, 5}, {2, 4, 6}}. If we define an equivalence relation by i ∼ j if i and j are
equivalent modulo 3, we obtain a non-trival G-congruence corresponding to the
block system {{1, 4}, {2, 5}, {3, 6}}. As for the trivial G-congruences, the equality
congruence corresponds to the block system {{1}, {2}, . . . , {6}} containing the
singletons, and the full congruence corresponds to the block system {{1, . . . , 6}}
that just contains the full set X.

Example 8. Consider the primitive cyclic group G = h(1, 2, 3, 4, 5)i ≤ S5 of
Example 2. With the notion of G-congruences, it is much easier to prove that
this group is primitive. Indeed, fix a G-congruence on X. By G-invariance, all
classes of the G-congruence must have the same size, say m. If the congruence
has n classes, then we have mn = |X| = 5. So m is either 1 or 5 since 5 is prime,
which means the classes are either singletons (giving the equality congruence) or
the full set X (giving the full congruence). Thus all G-congruences are trivial,
and thus G is primitive. Alternatively, we could make the same argument in
terms of block systems, using the fact that all blocks in a system have the same
size to show all blocks must be trivial. This argument actually shows that not
only are cyclic groups of prime order primitive, but all transitive groups of prime
degree are primitive (since |X| is the degree of a permutation group on X). 
2.2

Languages, Automata and State Complexity

Let Σ be a finite set. The set of all finite-length sequences of elements of Σ
is called the free monoid generated by Σ, and is denoted Σ ∗ . In this context,
elements of Σ are called letters, and elements of Σ ∗ are called words over Σ. The
operation of the free monoid is concatenation of words, and the identity element
is the empty word ε of length zero. A set L ⊆ Σ ∗ is called a language over Σ,
and Σ is called the alphabet of L.
We use the convention that a language L ⊆ Σ ∗ is implicitly a pair (L, Σ), so
for example, the language {a, ab} over alphabet {a, b} and the language {a, ab}
over alphabet {a, b, c} are distinct. In particular, two words over different alphabets are necessarily distinct. This is similar to the convention which views two
functions with different codomains as necessarily distinct.
A deterministic finite automaton (DFA) is a tuple A = (Q, Σ, δ, 1, F ) where
Q and Σ are finite sets, δ : Q × Σ ∗ → Q is a monoid action, 1 ∈ Q, and F ⊆ Q.
The elements of Q are called states; the state 1 is called the initial state and the
states in F are called final states. The set Σ is the alphabet of the automaton.
The monoid action δ is called the transition function.
9

Since Σ generates Σ ∗ , we may completely specify the action δ by defining
the function aδ : Q → Q for each a ∈ Σ. If w = a1 · · · ak for a1 , . . . , ak ∈ Σ,
then wδ : Q → Q is the composition (a1 )δ · · · (ak )δ . The function εδ : Q → Q
is necessarily the identity map. The monoid M (A) = {wδ : w ∈ Σ ∗ } is called
the transition monoid of A; it is a submonoid of TQ and thus has a natural
action on Q. We call the function wδ the action of w. Under our notational
conventions, we may write δ(p, w) = q as pwδ = q or simply pw = q. We may
also extend wδ by union and apply it to subsets of the state set: for X ⊆ Q we
w
have Xw = {qw : q ∈ X}. We also sometimes write p −→ q to mean pw = q.
A state q ∈ Q is reachable from p ∈ Q if pw = q for some w. Two states
p, q ∈ Q are distinguishable by X ⊆ Q if there exists w ∈ Σ ∗ such that pw ∈
X ⇔ qw 6∈ X. We frequently use two special cases of these definitions: A state
q ∈ Q is reachable if it is reachable from the initial state 1, and states p, q ∈ Q
are distinguishable if they are distinguishable by F . We say A is accessible if
every state is reachable (from the initial state 1), and strongly connected if every
state is reachable from every other state. A state q ∈ Q is empty if qw 6∈ F for
all w ∈ Σ ∗ . In a strongly connected DFA, there exists an empty state if and only
if all states are empty.
Consider the following relation on Q: two states p, q ∈ Q are related if and
only if they are indistinguishable by X ⊆ Q, that is, for all w ∈ Σ ∗ we have
pw ∈ X ⇔ qw ∈ X. This is an equivalence relation on Q, and in fact it is an
M (A)-congruence. Indeed, if p and q are equivalent, we have pw ∈ X ⇔ qw ∈ X
for all w ∈ Σ ∗ . So in particular, if we take w = xy for some fixed x ∈ Σ ∗ , then
(px)y ∈ X ⇔ (qx)y ∈ X for all y ∈ Σ ∗ , and thus px and qx are equivalent for
all x ∈ Σ ∗ . This congruence is called the indistiguishability congruence of X.
The language recognized by A or simply language of A is the language L(A) =
{w ∈ Σ ∗ : 1w ∈ F } over Σ. A language which can be recognized by a DFA
is called a regular language. Two DFAs are equivalent if they have the same
language. Two DFAs A = (Q, Σ, δ, 1, F ) and A′ = (Q′ , Σ ′ , δ ′ , 1′ , F ′ ) with Σ = Σ ′
are isomorphic if there is a bijection f : Q → Q′ such that 1f = 1′ , F f = F ′ ,
and (qaδ )f = (qf )aδ′ for all a ∈ Σ; in other words, they are identical up to the
naming of the states. In particular, isomorphic DFAs are equivalent.
We say A is minimal if the number of states is minimal among all DFAs
equivalent to A. It is well-known that for each regular language L, all minimal
DFAs recognizing L are isomorphic and hence have the same number of states.
The number of states in a minimal DFA for L is called the state complexity of L,
and is denoted sc(L). A DFA A is minimal if and only if all states are reachable
and all pairs of states are distinguishable.
Given a binary regular operation ◦, the state complexity of the operation ◦
is the following function:
(m, n) 7→ max{sc(Lm ◦ Kn ) : sc(Lm ) = m, sc(Kn ) = n}.
That is, it is the maximal state complexity of the language resulting from the
operation, expressed as a function of the state complexities of the operation’s
arguments.
10

For f : N × N → N and g : N × N → N, we say f ≤ g if f (m, n) ≤ g(m, n) for
all (m, n) ∈ N × N; we say that f is an upper bound for the state complexity of
the operation ◦ if sc(◦) ≤ f , and a tight upper bound if sc(◦) = f .
In the definition of state complexity of operations, we assume that ◦ takes
two languages over the same alphabet as arguments. This is justified by our view
that words over different alphabets are necessarily distinct; hence, for example,
the union of two languages over different alphabets would be a set containing
a mixture of words over different alphabets, which is not a language. To perform such an operation, one must first convert the operands to languages over a
common alphabet. This convention is very common in the literature; however,
Brzozowski has recently argued this convention is unnecessary, and in fact leads
to incorrect state complexity bounds for operations on languages over different alphabets, since converting the input languages to a common alphabet can
change their state complexities [7]. Brzozowski introduces a distinction between
restricted state complexity of operations, the traditional model in which operands
must have the same alphabet, and unrestricted state complexity of operations, a
new model which produces accurate state complexity bounds for operations on
languages over different alphabets.
We use restricted state complexity in this paper for the following reasons.
First, computing unrestricted state complexity requires using DFAs which have
an empty state, and in particular are not strongly connected. In this paper, we
mainly study DFAs whose transition monoids are permutation groups, which
are always strongly connected. This group-theoretic focus is essential to most of
our results. Working with DFAs that are not strongly connected would take us
into the realm of semigroup theory, and we are unsure how much of our work
would carry over. Second, restricted state complexity has been the dominant
model of state complexity of operations for many years, while unrestricted state
complexity is a recent generalization. Although restricted state complexity gives
incorrect results when applied to languages over different alphabets, it is otherwise a correct model. We have chosen to study the simpler case of restricted
state complexity in this paper and leave the more general unrestricted case for
potential future work.

3

Primitive Groups and Uniform Minimality

A DFA A = (Q, Σ, δ, 1, F ) is called a permutation DFA if M (A) is a permutation
group on Q. In this case we call M (A) the transition group rather than the
transition monoid. The languages recognized by permutation DFAs are called
group languages.
Proposition 1. For a permutation DFA A, the following are equivalent:
1. A is accessible.
2. A is strongly connected.
3. M (A) is transitive.
11

Proof. (1) ⇒ (3): Since A is accessible, for each q ∈ Q there exists wq ∈ Σ ∗
such that 1wq = q. Since M (A) is a group, the element wq has an inverse, and
thus for all p, q ∈ Q we have p(wp )−1 wq = 1wq = q. It follows M (A) is transitive.
(3) ⇒ (2): Since M (A) is transitive, for all p, q ∈ Q there exists w ∈ Σ ∗
such that pw = q. This is precisely saying that A is strongly connected.
The last implication (2) ⇒ (1) is immediate.
⊓
⊔
Note that (2) ⇔ (3) holds for arbitrary DFAs, not only permutation DFAs.
Let A = (Q, Σ, δ, 1, F ) be a DFA and let L = L(A) be its language. For
S ⊆ Q, we write A(S) for the DFA A = (Q, Σ, δ, 1, S) obtained by replacing the
final state set of A with S. We say a regular language L′ is a cognate of L if
L′ = L(A(S)) for some S ⊆ Q. We say a DFA A′ is a cognate of A if A′ = A(S)
for some S; so a language is a cognate of L if and only if it is recognized by a
cognate of A. If S = Q or S = ∅, then A(S) is called a trivial cognate of A,
since L(A(S)) is either Σ ∗ or the empty language ∅.
We say A is uniformly minimal if all non-trivial cognates of A are minimal.
That is, we can reassign the final state set of the DFA in any non-trivial way and
the new DFA will always be minimal. Equivalently, all cognates of L = L(A)
have the same state complexity |Q|. This definition is essentially restricted to
accessible DFAs, since if A is not accessible, then not all states are reachable
and hence no cognate of A can be minimal.
Restivo and Vaglica introduced and studied uniformly minimal DFAs in [17].
Their notion of uniform minimality is almost the same as ours, except it is
restricted to strongly connected DFAs. Presumably, Restivo and Vaglica were
interested in DFAs that are minimal for every reassignment of initial and final
states; if a DFA is not strongly connected, we can reassign the initial state to
obtain a new DFA which is not accessible and hence not minimal. However, for
strongly connected DFAs, the choice of initial state has no effect on minimality
since every state is reachable from each possible choice of initial state. Hence we
lose nothing by fixing an initial state and generalizing to accessible DFAs.
Remark. Restivo and Vaglica also studied uniformly minimal DFAs in [16], but
they used different terminology. They used the term “almost uniformly minimal”
for the notion discussed above, and used “uniformly minimal” for a stronger
condition that can only be met by incomplete DFAs (which we do not discuss in
this paper).
A DFA A is called simple if all M (A)-congruences are trivial. Ésik proved
the following result for strongly connected DFAs [17, Proposition 1]. The same
proof works for accessible DFAs.
Proposition 2. An accessible DFA A is uniformly minimal if and only if it is
simple.
Proof. Suppose A is simple, that is, all M (A)-congruences are trivial. Then in
particular, for every S ⊆ Q, the indistiguishability congruence of S is trivial. If
the indistiguishability congruence for S is the equality relation, then each state
12

lies in its own class, so all pairs of states are distinguishable. Since A is accessible, all states are reachable, and hence A is minimal. If the indistinguishability
congruence for S is the full relation, then all states are indistinguishable. But
final states are always distinguishable from non-final states, so this can only
happen if all states are final (S = Q) or all states are non-final (S = ∅). Hence
if ∅ ( S ( Q, then A(S) is minimal, so it follows that A is uniformly minimal.
Conversely, suppose A is not simple, and there exists a non-trivial M (A)congruence. Then this congruence has a class E which has at least two elements,
but is not all of Q. Let E be the final state set of A and let p, q ∈ E. For all
w ∈ Σ ∗ , the states pw and qw both lie in the set Ew, which is contained in some
congruence class E ′ . If E ′ = E, then we have pw, qw ∈ E. If E ′ ∩ E = ∅, then
we have pw, qw 6∈ E. Thus for all w ∈ Σ ∗ , we have pw ∈ E ⇔ qw ∈ E, and so
p and q are not distinguishable by E. Hence A is not uniformly minimal, since
A(E) is not minimal.
⊓
⊔
In the special case of permutation DFAs, we have:
Corollary 1. An accessible permutation DFA A is uniformly minimal if and
only if M (A) is primitive.
Proof. If A is uniformly minimal, then it is simple, so all M (A)-congruences are
trivial. Now, recall that a group G is primitive if and only if all G-congruences
are trivial. Since M (A) is a group, we see that M (A) is primitive.
Conversely, if M (A) is primitive, then all M (A)-congruences are trivial.
Hence A is simple and hence uniformly minimal.
⊓
⊔
Note that both implications in Corollary 1 are vacuously true if A is not accessible: A cannot be uniformly minimal, and M (A) cannot be transitive and thus
cannot be primitive. Thus one can technically omit the accessible assumption.
It seems this relationship between primitivity and minimality has been overlooked until recently. Primitive groups have seen increasing application in automata theory over the past decade, particularly in connection with the classical
synchronization problem for DFAs; for a survey of such work see [2]. The connection between simple DFAs and primitive groups was recently noted by Almeida
and Rodaro [1]. However, primitive groups are not mentioned in Restivo and
Vaglica’s work on uniformly minimal DFAs, nor in any other work on DFA minimality that we are aware of.
The wealth of results on primitive groups makes Corollary 1 quite useful for
studying and constructing uniformly minimal DFAs. For example, we can use
this corollary to easily prove that for each n ≥ 2, there exists a uniformly minimal
DFA with n states. Restivo and Vaglica proved this using a rather complicated
construction [16, Theorem 3].
Proposition 3. For each n ≥ 2, there exists a uniformly minimal permutation
DFA with n states.

13

Proof. The symmetric group Sn is primitive for all n ≥ 2, and clearly for each
n ≥ 2 there exists an n-state DFA with transition group Sn . For example, let
{g1 , . . . , gk } be a generating set of the symmetric group and let A be a DFA
with states {1, . . . , n}, alphabet Σ = {a1 , . . . , ak }, and transition function δ
with (ai )δ = gi for 1 ≤ i ≤ k. In fact we can use a binary alphabet, since Sn has
generating sets of size two for all n ≥ 2.
⊓
⊔
This proof illustrates a technique that is very useful for producing examples of
DFAs. If we have a generating set for a transformation monoid, we can construct
a DFA which has that monoid as its transition monoid.
Example 9. Let A be the DFA with alphabet {a, b} defined as follows.
– The states are {1, 2, 3, 4}, the initial state is 1, and the final states are {3, 4}.
– The transformations are the permutations a = (2, 3, 4) and b = (1, 2)(3, 4).
More formally, we mean that the transition function δ of A is given by aδ =
(2, 3, 4) and bδ = (1, 2)(3, 4). However, we will generally be brief when describing
DFAs, as above.
The permutations (1, 2)(3, 4) and (2, 3, 4) generate the alternating group A4 .
Thus the transition group of A is A4 . We saw in Example 4 that A4 is transitive
and primitive. Hence by Proposition 1, A is strongly connected, and by Corollary
1, A is uniformly minimal.
A state diagram of A is given in Figure 1. We can see from the diagram
that A is indeed strongly connected. It is tedious, but possible to verify that
A is uniformly minimal by checking that it is minimal with respect to every
non-empty, proper subset of {1, 2, 3, 4}.


a
a
a, b

b
1

a

2

3

4

b
b
Fig. 1. Uniformly minimal DFA A of Example 9.

a
1

a

2

a

3

a

4

a

5

a

6

Fig. 2. Non-minimal DFA A of Example 10 with an imprimitive transition group.

14

Example 10. Let A be the DFA with alphabet {a}, states {1, . . . , 6}, initial state
1, final states F = {1, 3, 5} and a = (1, 2, 3, 4, 5, 6). A diagram is in Figure 2.
The transition group G of A is the cyclic group of order six, which is imprimitive. We saw in Example 1 that F = {1, 3, 5} is a block for this group.
Hence for all k, we either have F ak = F or F ak ∩ F = ∅. Thus if i, j ∈ F , then
for all k we have iak ∈ F ⇔ jak ∈ F . This means all pairs of states in F are
indistinguishable by F , and hence A is not minimal.
This argument actually shows that whenever F is a non-trivial block of G,
the DFA A is not minimal. In fact, this also holds whenever F is a union of
non-trivial blocks of G (see Lemma 1 below).
Note that if we construct a DFA from a cyclic group of prime order, we get
a uniformly minimal DFA, since cyclic groups of prime order are primitive. 
There exist many infinite families of primitive groups, and hence of uniformly
minimal permutation DFAs. However, there are infinitely many positive integers
n for which the only primitive groups of degree n are Sn and An [12, pg. 66].
Hence other infinite families of primitive groups cannot be used to construct
n-state uniformly minimal DFAs for every n, unless we “fill in the gaps” with
symmetric or alternating groups.
Remark. Steinberg has extended the notion of primitivity to transformation
monoids [20]. Steinberg defines a transformation monoid M to be primitive if
there are no non-trivial M -congruences. Under this definition, an accessible DFA
A is uniformly minimal if and only if the transition monoid M (A) is primitive.
However, we have not investigated whether any of our other results that hold
for primitive groups are also true for primitive monoids.
We close this section with a technical lemma that generalizes Proposition 2.
If M is a transformation monoid on X and S ⊆ X, we say that S is saturated
by an M -congruence if it is a union of classes of the M -congruence.
Lemma 1. An accessible DFA A with ∅ ( F ( Q is minimal if and only if
there is no non-trivial M (A)-congruence that saturates F .
It follows that if all M (A)-congruences are trivial, then A is uniformly minimal.
Conversely, if there is a non-trivial M (A)-congruence, then it saturates its own
congruence classes and at least one class is a proper non-empty subset of Q, and
thus A is not uniformly minimal. Hence this indeed generalizes Proposition 2.
Proof. We prove the contrapositive: A is not minimal if and only if there exists
a non-trivial M (A)-congruence that saturates F .
Suppose A is not minimal. Then the indistinguishability congruence of F is
a non-trivial M (A)-congruence, since at least two states are indistinguishable.
Suppose there is an indistinguishability class E that is neither contained in F
nor disjoint from F . Then there exist p, q ∈ E such that p ∈ F and q 6∈ F .
But then p and q are distinguishable by F , which cannot happen since E is an
indistinguishability class. Thus for each indistinguishability class [q], we have
15

S
[q] ⊆ F or [q] ∩ F = ∅. Then we have F = f ∈F [f ], so F is saturated by its
indistinguishability congruence.
Conversely, let E1 , . . . , Ek ⊆ Q be the congruence classes of a non-trivial
M (A)-congruence that saturates F . Choose a congruence class Ei of size at
least two. Then for all w ∈ Σ ∗ we have Ei w ⊆ Ej for some j. Since F is a union
of congruence classes, either Ej ⊆ F or Ej ∩ F = ∅. Hence for p, q ∈ Ei and all
w ∈ Σ ∗ , we have pw ∈ F ⇔ Ej ⊆ F ⇔ Ei w ⊆ F ⇔ qw ∈ F . It follows that
states in Ei are indistinguishable, and thus A is not minimal.
⊓
⊔
In the special case of permutation DFAs, this has a useful consequence.
Corollary 2. Let A be a permutation DFA. If |F | = 1 or |F | = |Q| − 1, then A
is minimal if and only if it is accessible.
Proof. Recall that if G is a transitive permutation group and E and E ′ are
classes of a G-congruence, then |E| = |E ′ |. It follows that if |F | = 1, then a
non-trivial M (A)-congruence cannot saturate F since all the congruence classes
have size at least two. Furthermore, an M (A)-congruence saturates F if and only
if it saturates Q \ F , and if |F | = |Q| − 1 then a non-trivial M (A)-congruence
cannot saturate the set Q \ F of size one. Hence if A is accessible, it is minimal
by Lemma 1. On the other hand, if A is not accessible, it cannot be minimal. ⊓
⊔

4

Main Results

Throughout this section, A = (Q, Σ, δ, 1, F ) and A′ = (Q′ , Σ ′ , δ ′ , 1′ , F ′ ) are
minimal DFAs with a common alphabet Σ = Σ ′ . The languages of A and A′ are
L and L′ , and the transition monoids are M and M ′ , respectively. For w ∈ Σ ∗ ,
we write w for wδ ∈ M and w′ for wδ′ ∈ M ′ . Sometimes we will assume A and
A′ are permutation DFAs, and then we will use G and G′ for the transition
groups rather than M and M ′ .
4.1

Direct Products and Boolean Operations

The direct product of A and A′ is the DFA A×A′ with state set Q×Q′ , alphabet
a
Σ, transitions (q, q ′ ) −→ (qa, q ′ a′ ) for each (q, q ′ ) ∈ Q × Q′ and a ∈ Σ, initial
state (i, i′ ), and an unspecified set of final states. By assigning particular sets
of final states to A × A′ as described below, we can recognize the languages
resulting from arbitrary binary boolean operations on L and L′ .
Fix a function ◦ : {0, 1}2 × {0, 1}; these are called binary boolean functions.
For a set S, let χS : S → {0, 1} denote the characteristic function of S, defined
by χS (x) = 1 if x ∈ S and χS (x) = 0 otherwise. We can think of χS (x) as giving
the “truth value” of the proposition “ x ∈ S ”, where 0 is false and 1 is true. Now
for F ⊆ Q and F ′ ⊆ Q′ , define F ◦ F ′ = {(q, q ′ ) ∈ Q × Q′ : χF (q) ◦ χF ′ (q ′ ) = 1}.
Then A × A′ with final states F ◦ F ′ recognizes the language L ◦ L′ defined by
L ◦ L′ = {w ∈ Σ ∗ : χL (w) ◦ χL′ (w) = 1}.
16

For example, if ◦ : {0, 1}2 → {0, 1} is the “logical or” function, then L ◦ L′ =
L ∪ L′ , since w ∈ L ◦ L′ if w ∈ L or w ∈ L′ . Similarly, the “logical and” function
gives the intersection L ∩ L′ .
We say that a boolean function (and the associated boolean operation on
languages) is proper if its output depends on both of its arguments. For example,
u ◦ v = 1 − u (giving L ◦ L′ = Σ ∗ \ L) only depends on the first argument,
and u ◦ v = 0 (giving with L ◦ L′ = ∅) depends on neither argument, so they
are not proper. If L and L′ have state complexity m and n respectively, then
the improper binary boolean operations have state complexity 1 (if they are
constant), state complexity m (if they depend only on the first operand), or
state complexity n (if they depend only on the second operand). There are 16
binary boolean operations in total, and one may easily verify that 10 of them
are proper.
If A and A′ have m and n states respectively, A × A′ has mn states. Hence
every proper binary boolean operation has state complexity bounded by mn.
It is well-known that this bound is tight for general regular languages, and it
remains tight for regular group languages. In fact, the original witnesses for
union given by Maslov [15] and Yu et al. [21] are group languages, and we will
demonstrate later (in Example 13) that these languages are also witnesses for
all other proper binary boolean operations. We will say the pair (L, L′ ) has
maximal boolean complexity if sc(L ◦ L′ ) = sc(L) sc(L′ ) for all proper binary
boolean operations ◦.
Suppose that ∅ ( F ( Q and ∅ ( F ′ ( Q′ . We say a subset of Q × Q′
is (F, F ′ )-compatible if it is equal to F ◦ F ′ for some proper binary boolean
operation ◦. Notice that (L, L′ ) has maximal boolean complexity if and only if
A × A′ is minimal for every (F, F ′ )-compatible subset of Q × Q′ . We disallow
F = ∅ and F = Q since then A × A′ is minimal for F ◦ F ′ only if |Q| = 1
and L = ∅ or L = Σ ∗ ; these cases are uninteresting. Similarly, we exclude
F ′ = ∅ and F ′ = Q′ . We say the pair (A, A′ ) (or the direct product A × A′ ) is
uniformly boolean minimal if for every pair of sets (S, S ′ ) with ∅ ( S ( Q and
∅ ( S ′ ( Q′ and every (S, S ′ )-compatible set S ◦ S ′ , the DFA (A × A′ )(S ◦ S ′ )
is minimal. In other words, if every pair of cognates of L and L′ has maximal
boolean complexity.
We give an example of a pair of DFAs that are not uniformly boolean minimal,
as well as a pair of DFAs that are.
Example 11. Define two DFAs over alphabet Σ = {a, b, c} as follows:
– A has state set Q = {1, 2}, initial state 1, final state set F = {1}, and
transformations a = b = (1, 2), c = ().
– A′ has state set Q′ = {1, 2}, initial state 1, final state set F ′ = {1}, and
transformations a′ = c′ = (1, 2), b′ = ().
We show that (L(A), L(A′ )) does not have maximal boolean complexity, and
thus A × A′ is not uniformly boolean minimal.

17

To see this, consider the symmetric difference operator ⊕, arising from the
“exclusive or” boolean function: for u, v ∈ {0, 1}, the “exclusive or” u ⊕ v is zero
if u = v and one if u 6= v. The corresponding operation on languages over Σ is
L ⊕ L′ = {w ∈ Σ ∗ : w ∈ L or w ∈ L′ , but not both} = (L \ L′ ) ∪ (L′ \ L).
The final state set that makes A × A′ recognize L(A) ⊕ L(A′ ) is:
F ⊕ F ′ = {(q, q ′ ) ∈ Q × Q : q ∈ F or q ′ ∈ F ′ , but not both} = {(1, 2), (2, 1)}.
State diagrams of the DFAs A, A′ and (A × A′ )(F ⊕ F ′ ) are shown in Figure
3. Notice that (A × A′ )(F ⊕ F ′ ) is not minimal: the states (1, 2) and (2, 1)
cannot be distinguished. Since F ⊕ F ′ is an (F, F ′ )-compatible set, it follows
that (L(A), L(A′ )) does not have maximal boolean complexity, and that A × A′
is not uniformly boolean minimal.

c
c

1, 1

c

1, 2

a, b
1

c
2

a, b
b

b

b

a

a

a

b

a, c
1

a

b

b

2
a, c

c
2, 1

2, 2

c
Fig. 3. DFAs A, A′ and A × A′ of Example 11. The final state set of A × A′ is chosen
so that A × A′ recognizes the symmetric difference of the languages of A and A′ .

Example 12. Define two DFAs over alphabet Σ = {a, b} as follows:
– A has state set Q = {1, 2} and transformations a = (1, 2), b = ().
– A′ has state set Q′ = {1, 2, 3} and transformations a′ = (1, 2), b′ = (1, 2, 3).
The initial and final states are not important for this example.
The direct product A × A′ is shown in Figure 4. Notice that the transition
group of A′ is S3 . We will see much later (Corollary 3) that this implies A × A′
is uniformly boolean minimal.
Note that A × A′ is not uniformly minimal; for example, it is not minimal
with respect to the final state set {(1, 1), (1, 2), (1, 3)}. If |Q|, |Q′ | ≥ 2, a direct
product DFA with state set Q×Q′ can never be uniformly minimal. In particular,
it cannot be minimal for final state sets of the form S × Q′ (“unions of rows”)
or Q × S ′ (“unions of columns”). However, the definition of uniform boolean
minimality excludes these sets.

18

b
b

1, 1

1, 2

a

a

a

a

b

1, 3

a

2, 1

b

2, 2

b

a

2, 3

b

Fig. 4. Uniformly boolean minimal DFA A × A′ of Example 12.

Bell, Brzozowski, Moreira and Reis found sufficient conditions for a pair of
DFAs to be uniformly boolean minimal [3]. However, these conditions require
that the transition monoids of the DFAs contain the symmetric group, in the
sense that they contain every permutation of the DFA’s state set. In particular,
for permutation DFAs, these conditions only apply when the transition group
is the symmetric group on the state set. We obtain more general sufficient conditions for uniform boolean minimality in permutation DFAs, which apply to a
larger class of transition groups. Additionally, we show that DFAs whose transition monoids contain 2-transitive groups “usually” meet these conditions, up to
some technical assumptions we will state later.
We also obtain necessary and sufficient conditions for a pair of languages
(L, L′ ) to have maximal boolean complexity in the special case where L and L′
are recognized by permutation DFAs A and A′ with exactly one final state. In
this special case, it turns out (L, L′ ) has maximal boolean complexity if and
only if A × A′ is accessible. We give several group-theoretic conditions and a
graph-theoretic condition that are equivalent to A × A′ being accessible.
We begin with a proposition which characterizes (F, F ′ )-compatible subsets.
If Q is the state set of a DFA and S ⊆ Q, write S for Q \ S. Similarly, if L is a
language over Σ, write L for Σ ∗ \ L.
Proposition 4. Let ∅ ( F ( Q and ∅ ( F ′ ( Q′ . A subset of Q × Q′ is
(F, F ′ )-compatible if and only it is equal to one of the following sets:
(a)
(b)
(c)
(d)
(e)
(f )

F × F ′ (corresponding to L ∩ L′ ).
F × F ′ (corresponding to L ∩ L′ = L \ L′ ).
F × F ′ (corresponding to L ∩ L′ = L′ \ L).
F × F ′ (corresponding to L ∩ L′ = L ∪ L).
(F ×F ′ )∪(F ×F ′ ) (corresponding to symmetric difference (L\L′ )∪(L′ \L)).
The complement (Q × Q′ ) \ S, where S is one of the above sets.

Proof. Let ◦ be a proper binary boolean function. Let k be the number of pairs
(u, v) ∈ {0, 1} × {0, 1} such that u ◦ v = 1.
19

Case 1 (k = 1): If k = 1, then there is a unique pair (u, v) such that
u ◦ v = 1. Hence F ◦ F ′ = {(q, q ′ ) : χF (q) = u and χF ′ (q ′ ) = v}. Consider
possible values for (u, v):
–
–
–
–

If
If
If
If

(u, v) = (0, 0)
(u, v) = (0, 1)
(u, v) = (1, 0)
(u, v) = (1, 1)

then
then
then
then

F
F
F
F

◦ F′
◦ F′
◦ F′
◦ F′

=F
=F
=F
=F

× F ′.
× F ′.
× F ′.
× F ′.

Hence F ◦ F ′ is a set of type (a), (b), (c) or (d).
Case 2 (k = 2): If k = 2, there are exactly two pairs (u, v) and (u′ , v ′ )
such that u ◦ v = u′ ◦ v ′ = 1. We claim that u 6= u′ and v 6= v ′ . To see this,
suppose u = u′ . Then we must have v 6= v ′ , or else the pairs are not distinct.
Thus {v, v ′ } = {0, 1} and it follows u ◦ 0 = u ◦ 1 = 1. Hence ◦ only depends on
the value of the first argument, which contradicts the fact that ◦ is proper. By
a symmetric argument, we cannot have v = v ′ . Now, observe that (q, q ′ ) is in
F ◦ F ′ if and only if
χF (q) = u and χF ′ (q ′ ) = v or χF (q) = u′ and χF ′ (q ′ ) = v ′ .
Suppose (u, v) = (1, 0). Then we necessarily have (u′ , v ′ ) = (0, 1) and we get
F ◦ F ′ = (F × F ′ ) ∪ (F × F ′ ).
If (u, v) = (0, 1), then (u′ , v ′ ) = (1, 0) and we get the same set. If (u, v) = (1, 1)
or (u, v) = (0, 0), then we get
F ◦ F ′ = (F × F ′ ) ∪ (F × F ′ ).
But this is simply the complement of the previous set. So we either get a set of
type (e) or the complement of such a set, which is type (f).
Case 3 (k = 3): If k = 3, then there is a unique pair (u, v) such that
u ◦ v = 0. Hence F ◦ F ′ is the complement of a set of type (a), (b), (c) or (d),
that is, a set of type (f).
This proves that every (F, F ′ )-compatible set, that is, every set of the form
F ◦ F ′ where ◦ is a proper binary boolean function, has one of the given forms
(a)–(f). Conversely, if we are given sets F and F ′ and a set X ⊆ Q × Q′ with one
of the forms (a)–(f), the proof shows how to construct a proper binary boolean
function ◦ such that X = F ◦ F ′ . It follows X is (F, F ′ )-compatible if and only
if it has one of the forms (a)–(f).
⊓
⊔
4.2

Accessibility of A × A′

In this section, we consider the problem of determining when A×A′ is accessible.
This is essential for proving that A × A′ is minimal for a certain final state set,
and also an interesting question in its own right. Recall that by Proposition 1, the
DFA A × A′ is strongly connected if and only if the transition monoid of A × A′
is transitive. Furthermore, if A× A′ is a permutation DFA, then it is accessible if
and only if its transition group is transitive. The following proposition describes
the structure of the transition monoid of A × A′ .
20

Proposition 5. Let M× denote the transition monoid of A × A′ .
1. M× is isomorphic to the submonoid of M ×M ′ generated by {(a, a′ ) : a ∈ Σ}.
We often identify M× with this submonoid.
2. The projections π : M× → M and π ′ : M× → M ′ given by (w, w′ )π = w and
(w, w′ )π ′ = w′ are surjective.
3. If M and M ′ are groups, then M× is a group.
Proof. (1): Write w× for wA×A′ ∈ M× . Consider the map ϕ : M× → M × M ′
given by w× 7→ (w, w′ ). This map is clearly a monoid homomorphism. Furthermore, if (x, x′ ) = (y, y ′ ) then qx = qy and q ′ x′ = q ′ y ′ for all q ∈ Q and q ′ ∈ Q′ ,
and thus in M× we have (q, q ′ )x× = (q, q ′ )y× for all (q, q ′ ) ∈ Q × Q′ . Hence
x× = y× whenever x× ϕ = y× ϕ, and it follows that ϕ is injective.
Since ϕ is injective, (M× )ϕ is a finite monoid of the same size as M× . It
follows ϕ is bijective when viewed as homomorphism between M× and (M× )ϕ,
and thus ϕ is an isomorphism between these monoids. Since {a× : a ∈ Σ}
generates M× , we see that {(a, a′ ) : a ∈ Σ} generates (M× )ϕ. Hence we have
M× ∼
= (M× )ϕ = h(a, a′ ) : a ∈ Σi as required.
(2): Fix w ∈ M . Then for the element (w, w′ ) ∈ M× we have (w, w′ )π = w.
Hence π maps surjectively onto M . Similarly, π ′ maps surjectively onto M ′ .
(3): Since M× is a monoid, it suffices to show every element of M× has an inverse. Recall that the identity elements of M and M ′ are ε and ε′ respectively. For
(w, w′ ) ∈ M× , pick m and n such that wm = ε in M and (w′ )n = ε′ in M ′ . This
is possible since M and M ′ are finite groups. We have (wmn−1 , (w′ )mn−1 ) ∈ M× ,
and (w, w′ )(wmn−1 , (w′ )mn−1 ) = (wmn−1 , (w′ )mn−1 )(w, w′ ) = (wmn , (w′ )mn ) =
(ε, ε′ ), the identity of M× . Thus (wmn−1 , (w′ )mn−1 ) is an inverse of (w, w′ ). ⊓
⊔
Recall that for permutation DFAs A and A′ , we denote the transition group of
A by G and the transition group of A′ by G′ ; in this case we will also write
G× for the transition group of A × A′ . If A and A′ are permutation DFAs, the
transitivity of G× is a necessary and sufficient condition for all states of A × A′
to be reachable. However, the structure of G× can be difficult to understand.
Hence we will derive a simpler characterization of transitivity that depends only
on properties of G and G′ .
Suppose that A and A′ are permutation DFAs. Consider the subgroup ker π ≤
G× . It contains all (w, w′ ) ∈ G× such that w is the identity in G. View Q × Q′
as a grid, where elements of Q are “row indices” and elements of Q′ are “column indices”. Then ker π consists of the elements of G× which fix all row indices.
Hence we define R = ker π and call R the full row stabilizer. Similarly, C = ker π ′
fixes all column indices and we call it the full column stabilizer. Both of these
subgroups are normal, since they are kernels of homomorphisms.
Fix q ∈ Q and q ′ ∈ Q′ . Let (q, ∗) denote the set {(q, i′ ) ∈ Q × Q′ : i′ ∈ Q′ },
that is, the “q-th row” of Q × Q′ . Similarly, let (∗, q ′ ) = {(i, q ′ ) ∈ Q × Q′ : i ∈ Q}
denote the “q ′ -th column” of Q × Q′ . Let Rq ≤ G× be the setwise stabilizer of
(q, ∗) and let Cq′ ≤ G× be the setwise stabilizer of (∗, q ′ ). We call the subgroups
Rq the single row stabilizers and the subgroups Cq′ the single column stabilizers.
21

The full row stabilizer R is the intersection of all single row stabilizers, and hence
is a subgroup of each Rq ; the analogous fact holds for C.
We now give necessary and sufficient conditions for A × A′ to be transitive
in the case where A and A′ are permutation DFAs.
Lemma 2. Let A and A′ be permutation DFAs. The following are equivalent:
1. A × A′ is accessible.
2. G and G′ are transitive and for all q ∈ Q and q ′ ∈ Q′ , the subgroups Rq π ′ ≤
G′ and Cq′ π ≤ G are transitive.
3. G is transitive and Rq π ′ ≤ G′ is transitive for some q ∈ Q, or G′ is transitive
and Cq′ π ≤ G is transitive for some q ′ ∈ Q′ .
4. G× is transitive.
Proof. Since A × A′ is a permutation DFA, we see that (1) ⇔ (4). Also, the
implication (2) ⇒ (3) is immediate.
(3) ⇒ (4): Fix (i, i′ ), (j, j ′ ) ∈ Q × Q′ . Suppose that Rq π ′ is transitive for
some q ∈ Q; the case where some Cq′ π is transitive is symmetric.
– Since G is transitive, there exists x ∈ G such that ix = q. Let k ′ ∈ Q′ be the
x
element such that i′ x′ = k ′ . Then (i, i′ ) −→ (q, k ′ ).
– Since G is transitive, there exists y ∈ G such that qy = j in G.
– Since Rq π ′ ≤ G′ is transitive on Q′ , there exists z ′ ∈ Rq π ′ such that k ′ z ′ =
z
j ′ (y ′ )−1 . Since (z, z ′ ) ∈ Rq , we have qz = q. Hence (q, k ′ ) −→ (q, j ′ (y ′ )−1 ).
It follows that
x

y

z

(i, i′ ) −→ (q, k ′ ) −→ (q, j ′ (y ′ )−1 ) −→ (qy, j ′ ) = (j, j ′ ).
Thus G× is transitive on Q × Q′ , since for all elements (i, i′ ), (j, j ′ ) ∈ Q × Q′ ,
there exists an element of G× that maps one to the other.
(4) ⇒ (2): If G× is transitive, then for all q, i, j ∈ Q and q ′ , i′ , j ′ ∈ Q′ , there
exist x, y ∈ Σ ∗ such that
y

x

(q, i′ ) −→ (qx, i′ x′ ) = (q, j ′ ) and (i, q ′ ) −→ (iy, q ′ y ′ ) = (j, q ′ ).
Thus, we see that:
– Since qx = q, we have (x, x′ ) ∈ Rq , and since q ′ y ′ = q ′ , we have (y, y ′ ) ∈ Cq′ .
– For all i, j ∈ Q, there exists a word y ∈ Cq′ π ≤ G that maps i to j.
– For all i′ , j ′ ∈ Q′ , there exists a word x′ ∈ Rq π ′ ≤ G′ that maps i′ to j ′ .
Hence for all q ∈ Q and q ′ ∈ Q′ , we see that Rq π ′ is transitive on Q′ and Cq′ π
is transitive on Q. Since Cq′ π ≤ G and Rq π ′ ≤ G′ , it follows that G and G′ are
transitive.
This establishes a cycle of implications (2) ⇒ (3) ⇒ (4) ⇒ (2). Since we
also have (1) ⇔ (4), all the statements are equivalent.
⊓
⊔
22

This lemma reduces the problem of checking transitivity of G× to just checking the the transitivity of a row stabilizer on the column indices, or of a column
stabilizer on the row indices. The following proposition gives a graph-theoretic
interpretation of this idea, which may be easier to understand and apply. This
graph-theoretic condition for accessibility of A × A′ can easily be proved without appeal to group theory, but for illustrative purposes we will connect it with
condition (3) of Lemma 2.
Proposition 6. Let A and A′ be permutation DFAs. The following statements
are equivalent:
1. A is accessible and there exists q ∈ Q such that all states in (q, ∗) are reachable, or A′ is accessible and there exists q ′ ∈ Q′ such that all states in (∗, q ′ )
are reachable.
2. G is transitive and Rq π ′ ≤ G′ is transitive for some q ∈ Q, or G′ is transitive
and Cq′ π ≤ G is transitive for some q ′ ∈ Q′ .
Proof. (1) ⇒ (2): Suppose A is accessible, and there exists q ∈ Q such that
all states in (q, ∗) are reachable. Since A is an accessible permutation DFA, G is
transitive on Q.
To see that Rq π ′ ≤ G′ is transitive on Q′ , fix i′ , j ′ ∈ Q′ . Since all states in
(q, ∗) are reachable from the initial state (1, 1′ ) of A × A′ , there is some word
x
x ∈ G× such that (1, 1′ ) −→ (q, i′ ). Also, there is some y ∈ G× such that
y
(1, 1′ ) −→ (q, j ′ ). Since A × A′ is a permutation DFA, there is some z ∈ Σ ∗ such
that z = x−1 . Thus we have
y

z

(q, i′ ) −→ (1, 1′ ) −→ (q, j ′ ).
We see that zy maps q to itself, so z ′ y ′ ∈ Rq π ′ . Hence Rq π ′ is transitive on Q′ .
By a symmetric argument, if A′ is accessible and there exists q ′ ∈ Q′ such
that all states in (∗, q ′ ) are reachable, it follows that G′ is transitive on Q′ and
Cq′ π ≤ G is transitive on Q.
(2) ⇒ (1): Suppose G is transitive and Rq π ′ ≤ G′ is transitive for some
q ∈ Q. Since G is transitive, A is accessible. In particular, there exists w ∈ Σ ∗
w
such that 1w = q, and it follows that (1, 1′ ) −→ (q, 1′ w′ ) in A × A′ . Since Rq π ′ is
x
transitive on Q′ , for all q ′ ∈ Q there exists x ∈ Rq π ′ such that (q, 1′ w′ ) −→ (q, q ′ ).
′
Hence every state in (q, ∗) is reachable. In the case where G and some Cq′ π are
transitive, we can use a symmetric argument.
⊓
⊔
We now prove one of our main results, which gives necessary and sufficient
conditions for pairs of group languages recognized by DFAs with exactly one
final state to have maximal boolean complexity.

23

Theorem 1. Suppose |Q| ≥ 3 or |Q′ | ≥ 3. Let A and A′ be permutation DFAs
with exactly one final state. Then the following are equivalent:
1. A × A′ is accessible.
2. For all proper binary boolean operations ◦, the language L ◦ L′ has maximal
state complexity. That is, (L, L′ ) has maximal boolean complexity.
3. There exists a proper binary boolean operation ◦ such that the language L◦L′
has maximal complexity.
Determining whether A × A′ is accessible can be difficult in general. Perhaps the
easiest method is to use the graph-theoretic condition of Proposition 6, which
states that assuming A and A′ are accessible, the direct product A × A′ is
accessible if either of the following holds.
– There exists a row (q, ∗) such that all states in (q, ∗) are reachable.
– There exists a column (∗, q ′ ) such that all states in (∗, q ′ ) are reachable.
This reduces the problem to just checking reachability for a single row or column.
The group-theoretic conditions of Lemma 2 may also be used, but they are
perhaps harder to understand. Much later in the paper (Section 4.4) we will use
these to obtain simpler group-theoretic conditions for accessibility of A × A′ .
In particular, provided that A and A′ are both accessible, and also satisfy an
additional criterion called dissimilarity (which is usually easy to check), we have:
– If G or G′ is a transitive simple group, then A × A′ is accessible.
– If G or G′ is a primitive group, then A × A′ is accessible.
Proof (Theorem 1). The only difficult implication here is (1) ⇒ (2). Suppose
A × A′ is accessible; we want to show that L ◦ L′ has maximal state complexity
for every proper binary boolean operation ◦. That is, we want to show that all
pairs of states of A × A′ are distinguishable by each (F, F ′ )-compatible subset
of Q × Q′ .
Note that since A × A′ is accessible, by Lemma 2 we know that G× is transitive and that Rq π ′ ≤ G′ and Cq′ π ≤ G are transitive for all q ∈ Q and q ′ ∈ Q′ .
What this means is:
– For every pair of states (p, p′ ) and (q, q ′ ) of A × A′ , there exists a word
w
w ∈ Σ ∗ such that (p, p′ ) −→ (q, q ′ ). (Transitivity of G× )
– Fix a state q ∈ Q. For every pair of states i′ , j ′ ∈ Q′ , there exists a word
w
w ∈ Σ ∗ such that (q, i′ ) −→ (q, j ′ ). (Transitivity of Rq π ′ )
– Fix a state q ′ ∈ Q′ . For every pair of states i, j ∈ Q, there exists a word
w
w ∈ Σ ∗ such that (i, q ′ ) −→ (j, q ′ ). (Transitivity of Cq′ π)
We will use these facts repeatedly throughout the proof.
Let F = {f } and F ′ = {f ′ }, so that F × F ′ = {(f, f ′ )}. Let (p, p′ ) and (q, q ′ )
be distinct states of A×A′ that we wish to distinguish. We will show these states
are distinguishable with respect to each type of set described in Proposition 4.
24

We only need to consider types (a) through (e), since sets of type (f) are just
complements of sets of types (a) through (e), and two states are distinguishable
by a set X if and only if they are distinguishable by the complement of X.
Case 1 (States in the same row or same column): Suppose p = q, that
is, both states (p, p′ ) and (q, q ′ ) are in the same row. Then we necessarily have
p′ 6= q ′ , since the states are distinct.
w

– By transitivity of G× , for all r ∈ Q there exists w ∈ Σ ∗ such that (p, p′ ) −→
(r, f ′ ).
w
– Since p = q and p′ 6= q ′ , we have (q, q ′ ) −→ (r, s) for some s 6= f ′ . (Since w′
′
′
is a permutation, it must map p and q to different states.)
If r ∈ F , we have (r, f ′ ) ∈ F × F ′ and (r, s) ∈ F × F ′ . Hence we can distinguish
the states if the final state set is F × F ′ , F × F ′ , or (F × F ′ ) ∪ (F × F ′ ).
If r 6∈ F , we have (r, f ′ ) ∈ F × F ′ and (r, s) ∈ F × F ′ . Hence we can distinguish
the states if the final state set is F × F ′ or F × F ′ .
This covers all the possible sets of final states. If p 6= q and p′ = q ′ (that is,
the states are in the same column) we can use a symmetric argument.
Case 2 (States in different rows and different columns): Assume p 6= q
and p′ 6= q ′ . We consider each possible set of final states in turn.
F × F ′ : Here A × A′ has exactly one final state (f, f ′ ), so it is minimal by
Corollary 2.
F × F ′ : We make a few observations:
w

– By transitivity of G× , there exists w ∈ Σ ∗ such that (p, p′ ) −→ (f, f ′ ).
– Since p 6= q, p′ 6= q ′ and w is a permutation, we must have qw 6= f and
q ′ w′ 6= f ′ .
x
– Since Cf ′ π is transitive, there exists x ∈ Σ ∗ such (qw, f ′ ) −→ (f, f ′ ).
It follows that
w

x

(p, p′ ) −→ (f, f ′ ) −→ (f x, f ′ ),

w

x

(q, q ′ ) −→ (qw, q ′ w′ ) −→ (f, q ′ w′ x′ ).

– Since qwx = f , qw 6= f and x is a permutation, we have f x 6= f . It follows
that (f x, f ′ ) ∈ F × F ′ .
– Since f ′ x′ = f ′ , q ′ w′ 6= f ′ and x′ is a permutation, we have q ′ w′ x′ 6= f ′ . It
follows that (f, q ′ w′ x′ ) ∈ F × F ′ .
Hence wx maps (p, p′ ) to a non-final state and (q, q ′ ) to a final state. Thus we
have distinguished the two states.
F × F ′ : We can use a symmetric argument to the previous case.
w
F × F ′ : As in the case of F × F ′ , pick w such that (p, p′ ) −→ (f, f ′ ). Then
w
(q, q ′ ) −→ (qw, q ′ w′ ), which is in F × F ′ since qw 6= f and q ′ w′ 6= f ′ . Thus
w
w sends (q, q ′ ) to a final state. But (p, p′ ) −→ (f, f ′ ) is non-final, so we have
distinguished the states.

25

(F × F ′ ) ∪ (F × F ′ ): This is the most complicated case.
u

– By transitivity of G× , there exists u ∈ Σ ∗ such that (p, p′ ) −→ (f, r′ ), where
r′ 6= f ′ .
u
– We have (f, r′ ) ∈ F × F ′ , so u sends (p, p′ ) to a final state. If (q, q ′ ) −→
′ ′
(qu, q u ) is non-final, then u distinguishes the states, so we may assume
without loss of generality that it is final.
– We cannot have qu = f , since p 6= q and pu = f . Thus qu ∈ F . Since
(qu, q ′ u′ ) is final we therefore must have q ′ u′ ∈ F ′ , that is, q ′ u′ = f ′ .
Define r = qu; now we have reduced the problem to distinguishing two states of
the forms (f, r′ ) and (r, f ′ ), with r 6= f and r′ 6= f ′ .
Suppose |Q| ≥ 3; if we only have |Q′ | ≥ 3 we can use a symmetric argument
to the argument below.
– Since Cf ′ π is transitive and |Q| ≥ 3, there is a word v ∈ Σ ∗ such that
v
(f, f ′ ) −→ (s, f ′ ) for some s 6∈ {r, f }.
v
– It follows that (f, r′ ) −→ (s, r′ v ′ ), where r′ v ′ 6= f ′ .
v
– The state (s, r′ v ′ ) is in F × F ′ , and thus is non-final. If (r, f ′ ) −→ (rv, f ′ ) is
′
′
final, then v distinguishes (f, r ) and (r, f ). Hence we may assume without
loss of generality that (rv, f ′ ) is non-final.
– A non-final state either lies in F × F ′ or F × F ′ . Since f ′ ∈ F ′ , we must have
(rv, f ′ ) ∈ F × F ′ . But then rv = f .
Thus we have
u

v

(p, p′ ) −→ (f, r′ ) −→ (s, r′ v ′ ),

u

v

(q, q ′ ) −→ (r, f ′ ) −→ (f, f ′ ).

Now, apply v again to both states.
–
–
–
–

Since s 6= r and rv = f , we have sv 6= f .
Since f ′ v ′ = f ′ and r′ 6= f ′ , we have r′ v ′ 6= f ′ and r′ v ′ v ′ 6= f ′ .
v
It follows that (s, r′ v ′ ) −→ (sv, r′ v ′ v ′ ) ∈ F × F ′ , and thus is non-final.
v
However, recall that f v = s and s 6= f ; thus (f, f ′ ) −→ (s, f ′ ) is in F × F ′ .

Hence (p, p′ ) and (q, q ′ ) are distinguished by uv 2 .
We have shown that all pairs of states of A × A′ are distinguishable by all
(F, F ′ )-compatible sets of final states, and so this proves (1) ⇒ (2).
The implication (2) ⇒ (3) is immediate. For (3) ⇒ (1), just note that for
each proper binary boolean operation ◦, the language L ◦ L′ is recognized by
(A × A′ )(X) for some set of final states X. If (A × A′ )(X) is not accessible, then
it cannot be minimal and thus L ◦ L′ cannot have maximal state complexity. ⊓
⊔
Note that Example 11 gives a pair of languages recognized by two-state permutation DFAs which have maximal complexity for intersection, but not symmetric
difference (see also [3, Example 2]). Hence in the previous theorem, it was necessary to assume that at least one DFA has three or more states.

26

Note that Theorem 1 also holds in the following cases:
– A and A′ both have exactly one non-final state.
– A has exactly one final state and A′ has exactly one non-final state.
– A has exactly one non-final state and A′ has exactly one final state.
The same arguments we gave in Theorem 1 can be used in the above three
cases, but the role of each argument is changed. For example, consider the case
where A has one final state and A′ has one non-final state. Let F = {f } and
let F ′ = Q′ \ F ′ = {q ′ }. We can use the same arguments as in the original proof
of Theorem 1, except wherever F ′ appears we substitute F ′ . So for example, we
deal with the case of F × F ′ = {(f, q ′ )} by appealing to Corollary 2, just like
we did for F × F ′ in the original proof. This works because distinguishability
arguments are the same whether we distinguish with respect to a set of final
states or a set of non-final states.
We now apply Theorem 1 to show that the original witnesses for the maximal state complexity of union (found by Maslow and later by Yu, Zhuang and
Salomaa) are in fact witnesses for all proper binary boolean operations.
Example 13. In [15], Maslov defined two families of DFAs over alphabet {0, 1} as
follows, and claimed that the languages they recognize are witnesses for union.
The DFA A has states {S0 , . . . , Sm−1 } with S0 initial and Sm−1 final, and the
transitions are given by Si 0 = Si , Si 1 = Si+1 for i 6= m − 1, and Sm−1 1 = S0 .
The DFA B has states {P0 , . . . , Pn−1 } with P0 initial and Pn−1 final, and the
transitions are given by Pi 1 = Pi , Pi 0 = Pi+1 for i 6= n − 1, and Pn−1 0 = P0 .
It is easy to see that A × B is accessible: the state (Si , Pj ) can be reached from
(S0 , P0 ) via the word 1i 0j . Furthermore, A and B are permutation DFAs: the
symbol 0 acts as the identity permutation in A and as a cyclic permutation of
the states in B, while 1 acts as a cyclic permutation in A and the identity in
B. They also have exactly one final state. So in fact, for m, n ≥ 3, the pair of
languages (L(A), L(B)) has maximal boolean complexity by Theorem 1. That
is, Maslov’s languages are witnesses for all proper binary boolean operations, in
addition to union.
Yu, Zhuang and Salomaa gave a different family of witnesses in [21]. For a
word w ∈ Σ ∗ and a ∈ Σ, let |w|a denote the number of occurrences of the letter
a in w. Yu et al. defined languages Lm = {w ∈ {a, b}∗ : |w|a ≡ 0 (mod m)}
and Ln = {w ∈ {a, b}∗ : |w|b ≡ 0 (mod n)}, then proved that Lm ∩ Ln and
Lm ∪ Ln both have state complexity mn. In fact, (Lm , Ln ) has maximal boolean
complexity for m, n ≥ 3. Indeed, one may verify that the minimal DFA of Lm
has m states, with the initial and final states equal; the letter a acts as a cyclic
permutation of the state set, and the letter b acts as the identity. The minimal
DFA of Ln is similar, except there are n states, b is the cyclic permutation, and a
is the identity. These DFAs are almost identical to the DFAs defined by Maslov,
except with a different choice of final state. This does not change the fact that
they are permutation DFAs with one final state and an accessible direct product,
and hence meet the conditions of Theorem 1.

27

4.3

Uniform Boolean Minimality

We now give sufficient conditions for a pair of permutation DFAs (A, A′ ) to be
uniformly boolean minimal. Just as with uniform minimality, primitive groups
play an important role in our conditions for uniform boolean minimality. To
state our conditions, we need some new notation.
For p, q ∈ Q and p′ , q ′ ∈ Q′ , we write Rp,q for the setwise stabilizer of
(p, ∗) ∪ (q, ∗), and Cp′ ,q′ for the setwise stabilizer of (∗, p′ ) ∪ (∗, q ′ ). If p = q
then Rp,q = Rp = Rq , and similarly if p′ = q ′ then Cp′ ,q′ = Cp′ = Cq′ . We call
these subgroups double row stabilizers and double column stabilizers. Under this
definition, single row stabilizers are special cases of double row stabilizers, and
similarly for column stabilizers.
Note that Rp and Rq are not necessarily subgroups of Rp,q , nor the other
way around: the group Rp might contain elements that map q to some state
r 6∈ {p, q}, while the group Rp,q might contain elements that swap p and q.
However, the full row stabilizer R is a common subgroup of Rp , Rq and Rp,q .
The analogous facts hold for column stabilizers.
Lemma 3. Suppose A and A′ are permutation DFAs.
1. If |Q| ≥ 3, the group G is primitive, and Rp,q π ′ ≤ G′ is primitive for all
p, q ∈ Q, then A × A′ is uniformly boolean minimal.
2. If |Q′ | ≥ 3, the group G′ is primitive, and Cp′ ,q′ π ≤ G is primitive for all
p′ , q ′ ∈ Q′ , then A × A′ is uniformly boolean minimal.
Note that we do not require p 6= q or p′ 6= q ′ , so in case (1) both the single and
double row stabilizers must be primitive, and in case (2) both the single and
double column stabilizers must be primitive.
Proof. Suppose that the conditions of (1) hold, that is, |Q| ≥ 3, G is primitive
and for all p, q ∈ Q, the subgroup Rp,q π ′ ≤ G′ is primitive. The case where the
conditions of (2) hold is symmetric. We want to show that for every pair of sets
∅ ( S ( Q and ∅ ( S ′ ( Q′ and each (S, S ′ )-compatible subset X ⊆ Q × Q′ ,
the DFA (A × A′ )(X) is minimal.
It suffices to consider the cases where X = S × S ′ and where X = (S × S ′ ) ∪
(S ×S ′ ). It may seem that this would only cover sets of type (a) and complements
of sets of type (e) from Proposition 4. However, these two cases actually cover
all possible types of (S, S ′ )-compatible sets.
To see this, consider a set S ×S ′ of type (b). If we prove that (A×A′ )(T ×T ′ )
is minimal for all pairs of sets ∅ ( T ( Q and ∅ ( T ′ ( Q′ , then in particular
we can take T = S and T ′ = S ′ to show that (A × A′ )(S × S ′ ) is covered. A
similar argument works for sets of type (c) and (d) .
Now note that if (A × A′ )(X) is minimal, then (A × A′ )(X) is also minimal,
so we also cover sets of type (e) and (f). So all types of sets from Proposition 4
are covered by just looking at the cases X = S × S ′ and X = (S × S ′ ) ∪ (S × S ′ ).
Let (i, i′ ) and (j, j ′ ) be distinct states of A × A′ ; we will show they are
distinguishable with respect to X.
Case 1 (States in the same row): Suppose i = j, that is, the states are
in the same row. Since the states are distinct, we have i′ 6= j ′ .
28

– Since G is primitive, it is transitive, and thus there exists a word w ∈ G that
w
w
maps i = j to some element s ∈ S. Thus (i, i′ ) −→ (s, i′ w′ ) and (j, j ′ ) −→
′ ′
(s, j w ).
– Suppose w does not distinguish (i, i′ ) and (j, j ′ ) with respect to X. Then
(s, i′ w′ ) ∈ X ⇔ (s, j ′ w′ ) ∈ X.
– Since Rs π ′ is primitive, all permutation DFAs with state set Q′ and transition group Rs π ′ are uniformly minimal by Corollary 1. It follows there exists
x′ ∈ Rs π ′ that distinguishes i′ w′ and j ′ w′ with respect to S ′ .
We have:
w

x

(i, i′ ) −→ (s, i′ w′ ) −→ (s, i′ w′ x′ ),

w

x

(j, j ′ ) −→ (s, j ′ w′ ) −→ (s, j ′ w′ x′ ).

– Since x′ distinguishes i′ w′ and j ′ w′ with respect to S ′ , we see that i′ w′ x′ ∈
S ⇔ j ′ w′ x′ 6∈ S.
– Hence (s, i′ w′ x′ ) ∈ S × S ′ ⇔ (s, j ′ w′ x′ ) ∈ S × S ′ .
It follows that either w or wx distinguishes (i, i′ ) and (j, j ′ ) with respect to X,
regardless of whether we have X = S × S ′ or X = (S × S ′ ) ∪ (S × S ′ ).
Case 2 (States in the same column): Suppose i′ = j ′ , that is, the states
are in the same column but different rows. Since G is primitive, all permutation
DFAs with state set Q and transition group G are uniformly minimal. Hence
there exists x ∈ G that distinguishes i and j with respect to S. Suppose without
loss of generality that ix ∈ S and jx 6∈ S. Since Rix,jx π ′ is primitive, it is
transitive, and thus there exists y ′ ∈ Rix,jx π ′ such that i′ x′ y ′ ∈ S. If y fixes ix
and jx, then (ixy, i′ x′ y ′ ) = (ix, i′ x′ y ′ ) ∈ S ×S ′ , and (jxy, j ′ x′ y ′ ) = (jx, j ′ x′ y ′ ) ∈
S×S ′ since i′ = j ′ implies i′ x′ y ′ = j ′ x′ y ′ . If y swaps ix and jx then (ixy, i′ x′ y ′ ) =
(jx, i′ x′ y ′ ) ∈ S × S ′ and (jxy, j ′ x′ y ′ ) = (ix, j ′ x′ y ′ ) ∈ S × S ′ . In either case, it
follows that xy distinguishes (i, i′ ) and (j, j ′ ) with respect to X, regardless of
whether we have X = S × S ′ or X = (S × S ′ ) ∪ (S × S ′ ).
Case 3 (States in different rows and different columns): Suppose
i 6= i′ and j 6= j ′ . We divide this case into two subcases.
Subcase 3a (X = S × S ′ ): We may assume without loss of generality that
(i, i′ ) and (j, j ′ ) are both in X. To see this, observe that since G is transitive and
Rq π ′ ≤ G′ is transitive for each q ∈ Q, we know that G× is transitive by Lemma
2. Thus there exists w ∈ Σ ∗ that maps (i, i′ ) to a state in X. Hence either w
distinguishes the states, or w also maps (j, j ′ ) into X.
Suppose we have (i, i′ ), (j, j ′ ) ∈ X = S × S ′ . Since Ri,j π ′ is primitive, there
exists w ∈ Ri,j π ′ that distinguishes i′ and j ′ with respect to S ′ . Without loss of
generality, assume i′ ∈ S ′ and j ′ 6∈ S ′ . Then (i, i′ )(w, w′ ) = (i, i′ ) ∈ S × S ′ and
(j, j ′ )(w, w′ ) ∈ S × S ′ . Hence w distinguishes the states.
Subcase 3b (X = (S × S ′ ) ∪ (S × S ′ )): This is the final case we must
deal with, and most complicated part of the proof. We introduce a notion of
polarity to simplify the arguments. We assign a polarity of 1 or −1 to each state
in Q × Q′ as follows. First, let q ∈ Q have polarity 1 if q ∈ S and polarity −1
if q 6∈ S. Similarly, q ′ ∈ Q′ has polarity 1 if q ′ ∈ S ′ and polarity −1 if q ′ 6∈ S ′ .
Then the polarity of (q, q ′ ) ∈ Q × Q′ is the product of the polarities of q and q ′ .
29

Next, we partition Q×Q′ into four quadrants: S×S ′ , S×S ′ , S×S ′ , and S×S ′ .
Notice that in each quadrant, all states have the same polarity. Furthermore, the
set X = (S × S ′ ) ∪ (S × S ′ ) is the set of all states with positive polarity, and the
set X = (S × S ′ ) ∪ (S × S ′ ) is the set of all states with negative polarity. Hence
to show all states are distinguishable by X, we must show that for each pair of
states of equal polarity, there is a word that preserves the polarity of one state
and reverses the polarity of the other state.
We now prove two claims, which together complete the proof of this subcase.
First we show that pairs of states in the same quadrant are distinguishable, and
then we show that pairs of states in different quadrants are distinguishable.
Claim 1 (States in the same quadrant are distinguishable): Suppose
(i, i′ ) and (j, j ′ ) are in the same quadrant. This means that (i, i′ ) and (j, j ′ ) have
the same polarity; furthermore, i and j have the same polarity, and i′ and j ′
have the same polarity.
– Choose a word w′ ∈ Ri,j π ′ that distinguishes i′ and j ′ with respect to S ′
(by primitivity of Ri,j π ′ ).
– Notice that w preserves the polarity of both i and j, since it either fixes both
i and j or it swaps them, and i and j have the same polarity.
– Since (i, i′ ) and (j, j ′ ) are in the same quadrant, we either have i′ , j ′ ∈ S ′ or
i′ , j ′ ∈ S ′ .
– Since w′ distinguishes i′ and j ′ with respect to S ′ , it follows that w′ acts on
i′ and j ′ by preserving the polarity of one state and reversing the polarity
of the other.
It follows that (w, w′ ) acts on (i, i′ ) and (j, j ′ ) by preserving the polarity of one
state and reversing the polarity of the other. In other words, w distinguishes
these states.
Claim 2 (States in different quadrants are distinguishable): Suppose
that (i, i′ ) and (j, j ′ ) lie in different quadrants.
– We may assume without loss of generality that (i, i′ ) and (j, j ′ ) have the
same polarity; otherwise they are trivially distinguishable.
– We may also assume without loss of generality that (i, i′ ), (j, j ′ ) ∈ X, by the
same argument we used in Subcase 3a. Thus we must have (i, i′ ) ∈ S × S ′
and (j, j ′ ) ∈ S × S ′ , or vice versa.
– We may assume without loss of generality that (i, i′ ) ∈ S × S ′ and (j, j ′ ) ∈
S × S ′ , by swapping the names of (i, i′ ) and (j, j ′ ) if necessary.
So we have reduced to the case where one state is in quadrant S × S ′ and the
other is in quadrant S × S ′ .
– Since G is primitive, S and S are either not blocks, or they are trivial blocks.
– S and S are proper non-empty subsets of Q, so they can only be trivial
blocks if |S| = |S| = 1.
– This would imply |Q| = |S| + |S| = 2, and we are assuming |Q| ≥ 3, so
they cannot both be trivial blocks. So at least one of S or S is not a block.
Note that in the case where G′ is primitive and the groups Ci′ ,j ′ π ≤ G are
primitive, we would use |Q′ | ≥ 3 here.
30

If S is not a block, let w ∈ G be a word such that ∅ ( Sw ∩ S ( S. Otherwise,
S is not a block, so let w ∈ G be a word such that ∅ ( Sw ∩ S ( S.
Now, we partition Q into two sets:
P = {q ∈ S : qw ∈ S} ∪ {q ∈ S : qw ∈ S},
P = {q ∈ S : qw ∈ S} ∪ {q ∈ S : qw ∈ S}.
Note that P is non-empty, since if it was empty we would have Sw ∩ S = ∅ and
Sw∩S = ∅. Similarly, P is non-empty, since otherwise we would have Sw∩S = S
and Sw ∩ S = S.
Observe that if i, j ∈ P , then P is a proper subset of Q with size at least
two, so it cannot be a block for G. Hence some word in G distinguishes i and j
by P . Similarly, if i, j ∈ P , then i and j are distinguishable by P . So we may
assume that either i ∈ P and j ∈ P , or i ∈ P and j ∈ P .
Suppose that i ∈ P and j ∈ P . Recall that we have (i, i′ ) ∈ S × S ′ and
(j, j ′ ) ∈ S × S ′ . Thus since i ∈ S we have iw ∈ S, and since j ∈ S we have
jw ∈ S. Hence (iw, i′ w′ ), (jw, j ′ w′ ) ∈ S × Q′ , that is, w maps both (i, i′ ) and
(j, j ′ ) into S × Q′ . There are two possibilities:
– The states (iw, i′ w′ ) and (jw, j ′ w′ ) are in the same quadrant, and thus are
distinguishable by Claim 1.
– The states (iw, i′ w′ ) and (jw, j ′ w′ ) are in different quadrants. Since iw and
jw are both in S, one state must lie in S × S ′ and the other S × S ′ . Thus w
distinguishes (i, i′ ) and (j, j ′ ), and we are done.
So if i ∈ P and j ∈ P , we have proved the claim. If we have i ∈ P and j ∈ P ,
then we have iw ∈ S and jw ∈ S, and so a symmetric argument shows that the
states are distinguishable. This completes the proof of Claim 2. By Claim 1 and
Claim 2, we see that all pairs of states are distinguishable by sets of the form
(S × S ′ ) ∪ (S × S ′ ), completing the proof of Subcase 3b and hence Case 3.
We have shown that for every pair of sets ∅ ( S ( Q and ∅ ( S ′ ( Q′ and
each (S, S ′ )-compatible subset X ⊆ Q × Q′ , each pair of states in (A × A′ )(X)
is distinguishable by X. Thus A × A′ is uniformly boolean minimal.
⊓
⊔
While Lemma 3 gives sufficient conditions for uniform boolean minimality,
the conditions are not necessary. We will demonstrate this later, in Example 20.
In the above proof, most of the difficulty came from dealing with the case
(S ×S ′ )∪(S ×S ′ ), which corresponds to the operation of symmetric difference (or
complement of symmetric difference). In fact, if we choose to ignore the operation
of symmetric difference, we can obtain necessary and sufficient conditions for the
corresponding weaker version of uniform boolean minimality.
Proposition 7. Suppose A and A′ are permutation DFAs. The following are
equivalent:
1. Rq π ′ ≤ G′ and Cq′ π ≤ G are primitive for all q ∈ Q and q ′ ∈ Q′ .
2. For all sets ∅ ( S ( Q and ∅ ( S ′ ( Q′ , the DFA (A × A′ )(S × S ′ ) is
minimal.
31

Proof. (1) ⇒ (2): We proceed as in the proof of Lemma 3. Let (i, i′ ) and (j, j ′ )
be distinct states of A × A′ ; we will show they are distinguishable with respect
to S × S ′ .
Case 1 (States in the same row): In the proof of Lemma 3, we proved that
states in the same row are distinguishable, using the facts that G is transitive and
Rq π ′ is primitive for all q ∈ Q. Those facts still hold under our new hypotheses,
so the same argument can be used here.
Case 2 (States in the same column): The argument we used for this case
in Lemma 3 relied on the double row stabilizers being transitive, so we cannot
use it here. However, under our new hypotheses, we know that G′ is transitive
and Cq′ π is primitive for all q ′ ∈ Q. Thus we can just use a symmetric argument
to the one for states in the same row.
Case 3 (States in different rows and different columns): Suppose
i 6= j and i′ 6= j ′ . As in the proof of Lemma 3, we may assume without loss
of generality that (i, i′ ), (j, j ′ ) ∈ S × S ′ . Since Ci′ π ′ is primitive, there exists
w ∈ Ci′ π that distinguishes i and j with respect to S. We claim that we can
choose w so that iw ∈ S and jw 6∈ S:
– Suppose for a contradiction that for all words w ∈ Ci′ π which distinguish i
and j by S, we have iw 6∈ S and jw ∈ S.
– Fix x ∈ Ci′ π such that ix 6∈ S and jx ∈ S.
y
– By transitivity of Ci′ π, we can choose y ∈ Ci′ π such that (ixy, i′ ) −→ (jx, i′ ).
It follows ixy = jx, and thus ixy ∈ S.
– Suppose jxy 6∈ S. Then we have ixy ∈ S and jxy 6∈ S, where xy ∈ Ci′ π. This
contradicts our assumption that for all words w ∈ Ci′ π which distinguish i
and j by S, we must have iw 6∈ S and jw ∈ S.
– Thus we can assume jxy ∈ S. But then since ixy = jx, we have ixy 2 =
jxy ∈ S. If jxy 2 6∈ S, we get a contradiction as before, so jxy 2 ∈ S.
– In general, we have ixy k = jxy k−1 , and it follows by induction on k that
ixy k ∈ S and jxy k ∈ S for all k > 1.
– But Ci′ π is a finite group, so y k = ε for some k. This gives ixy k = ix ∈ S
and jxy k = jx ∈ S, which contradicts the fact that ix 6∈ S.
This proves the claim; there must exist w ∈ Ci′ π such that iw ∈ S and jw 6∈ S.
w
w
Then we have (i, i′ ) −→ (iw, i′ ) ∈ S × S ′ , but (j, j ′ ) −→ (jw, j ′ w′ ) 6∈ S × S ′ since
jw 6∈ S. Thus w distinguishes the states. We have now shown that all pairs of
states (i, i′ ) and (j, j ′ ) are distinguishable.
(2) ⇒ (1): Suppose that for all sets ∅ ( S ( Q and ∅ ( S ′ ( Q′ , the DFA
(A × A′ )(S × S ′ ) is minimal. Assume for a contradiction that there exists q ′ ∈ Q′
such that Cq′ π is not primitive. Then there exists a non-trivial block B ( Q for
Cq′ π. We claim that (A × A)(B × {q ′ }) is not minimal:
– Since B is a non-trivial block, it contains at least two distinct elements. Let
i, j ∈ B be distinct and consider the states (i, q ′ ) and (j, q ′ ) of A × A′ .
– If q ′ w′ 6= q ′ , then w does not distinguish (i, q ′ ) and (j, q ′ ). Indeed, if q ′ w′ 6= q ′ ,
then (iw, q ′ w′ ) and (jw, q ′ w′ ) both lie outside of B × {q ′ }.
32

– Hence if w ∈ Σ ∗ distinguishes (i, q ′ ) and (j, q ′ ), we must have q ′ w′ = q ′ , and
thus w ∈ Cq′ π.
– Since B is a block for Cq′ π, we either have iw, jw ∈ B (if Bw = B) or
{iw, jw} ∩ B = ∅ (if Bw ∩ B = ∅).
– Thus w ∈ Cq′ π cannot distinguish (i, q ′ ) and (j, q ′ ): if iw, jw ∈ B then w
maps both states to B × {q}; otherwise it maps both states to B × {q}.
– It follows that no word can distinguish (i, q ′ ) and (j, q ′ ) by B × {q ′ }.
This shows that (A × A′ )(B × {q ′ }) is not minimal, which is a contradiction.
It follows that Cq′ π must be primitive for all q ′ ∈ Q′ . A symmetric argument
shows that Rq π ′ must be primitive for all q ∈ Q.
⊓
⊔
One may wonder whether condition (1) of Proposition 7 are actually sufficient
to prove Lemma 3. We will show later (Example 19) that this is not the case.
4.4

Dissimilar DFAs

While the conditions of Lemma 3 are somewhat complicated, there are cases
where we can easily verify that they hold. We consider some of these cases next.
We will say that the DFAs A and A′ are similar if the maps π : M× → M and
′
π : M× → M ′ are injective. By Proposition 5, π and π ′ are always surjective,
so if they are also injective then they are isomorphisms. Hence if A and A′ are
similar, the map π −1 π ′ : M → M ′ given by w 7→ w′ is a well-defined monoid
isomorphism. If A and A′ are not similar, we say they are dissimilar. If π and
π ′ both fail to be injective, we say that A and A′ are strongly dissimilar.
We give some examples of dissimilar DFAs. All DFAs will be over the twoletter alphabet {a, b}, and we will not specify the initial and final states since
they do not affect whether DFAs are similar.
Example 14. Let A have states {1, 2} and transformations a = (1, 2) and b = ().
Let A′ have states {1, 2} and transformations a′ = () and b′ = (1, 2). Notice that
in the transition group of A×A′ , we have (b, b′ ) = ((), (1, 2)) and (ε, ε′ ) = ((), ()).
Thus (b, b′ )π = (ε, ε′ )π = () and it follows that π is not injective. Hence A and
A′ are dissimilar. In fact, a symmetric argument shows that π ′ is not injective,
and thus these DFAs are strongly dissimilar.
Another way to see that these DFAs are dissimilar is to consider the “map”
w 7→ w′ . This “map” is not actually well-defined, since from the fact that b 7→ b′
we must have () 7→ (1, 2), but from the fact that ε 7→ ε′ we must have () 7→ ().
(Formally, this “map” is a binary relation; we say it is “well-defined” if the
relation happens to be a function, and otherwise is not.) This means A and
A′ cannot be similar, since we know that if they are similar, then π −1 π ′ is a
well-defined isomorphism which sends w to w′ .
Alternatively, without even checking whether the “map” w 7→ w′ is well
defined, we can see that since () = b 7→ b′ = (1, 2), this “map” sends an element
of order one to an element of order two, and thus it cannot possibly be a group
isomorphism. But then A and A′ cannot be similar.

33

Usually, the easiest way to prove that a pair of DFAs is dissimilar is to
examine the “map” w 7→ w′ and show that either it is not well-defined or not
an isomorphism.
Example 15. Let A have states {1, 2} and transformations a = (1, 2), b = (1, 2).
Let A′ have states {1, 2, 3, 4} and transformations a′ = (1, 2)(3, 4), b = (1, 3)(2, 4).
The transition group of A has two elements: ε = () and a = b = (1, 2). However,
the transition group of A′ has four elements:
ε = (), a′ = (1, 2)(3, 4), b′ = (1, 3)(2, 4), a′ b′ = (1, 4)(2, 3).
Hence these DFAs must be dissimilar, since they have different transition groups.
Similar DFAs always have isomorphic transition monoids/groups.
These DFAs are not strongly dissimilar. To see this, observe that the transition group of A × A′ has four elements:
(ε, ε′ ) = ((), ()),

(a, a′ ) = ((1, 2), (1, 2)(3, 4)),

(b, b′ ) = ((1, 2), (1, 3)(2, 4)),

(ab, a′ b′ ) = ((), (1, 4)(2, 3)).

It is easy to verify that any other product of elements will be equal to one of
these four. Now note that π ′ is a bijection but π is not, and thus A and A′
are not strongly dissimilar. In this case, the “map” w 7→ w′ is not well-defined.
However, the map (π ′ )−1 π given by w′ 7→ w is well-defined, and in fact is a
group homomorphism (but not an isomorphism).

As for examples of similar DFAs, we have the following fact: isomorphic DFAs
are necessarily similar. Indeed, suppose there is an isomorphism f : Q → Q′ .
Then for all q ∈ Q and a ∈ Σ, we have (qa)f = (qf )a′ , and thus qa = q(f a′ f −1 ).
It follows that a = f a′ f −1 for all a ∈ Σ ∗ , and thus w = f w′ f −1 for all w ∈ Σ ∗ .
Hence π : M× → M is given by (w, w′ )π = (f w′ f −1 , w′ )π = f w′ f −1 , and this
map is clearly injective since if f w′ f −1 = f x′ f −1 then w′ = x′ . Similarly, we
have w′ = f −1 wf and π ′ : M× → M is injective.
This shows that DFA similarity is a generalization of DFA isomorphism.
However, the next example shows that it is possible for two DFAs with different
numbers of states to be similar, and that the monoid isomorphism w 7→ w′ does
not necessarily have to be conjugation by a permutation.
Example 16. Consider the symmetric group S10 . This group contains an intransitive subgroup that is isomorphic to S5 , given by permutations of {1, . . . , 10}
which fix every point in {6, . . . , 10}. This can be considered the “natural” embedding of S5 in S10 . However, there is also a primitive subgroup of S10 that
is isomorphic to S5 , and is not conjugate to this natural embedding. In GAP’s
library of primitive groups, this subgroup can be accessed with the command
PrimitiveGroup(10,2). We can use GAP to compute an explicit isomorphism
between S5 and this subgroup:
gap> IsomorphismGroups(SymmetricGroup(5),PrimitiveGroup(10,2));
[ (3,4), (1,2,3)(4,5) ] ->
[ (1,2)(6,8)(7,9), (2,6,4,5,3,7)(8,10,9) ]
34

The GAP output tells us that the map which sends (3, 4) to (1, 2)(6, 8)(7, 9) and
(1, 2, 3)(4, 5) to (2, 6, 4, 5, 3, 7)(8, 10, 9) can be extended multiplicatively to an
isomorphism between S5 and the aforementioned primitive subgroup of S10 . We
use this isomorphism to construct similar permutation DFAs of different sizes.
Let A have states {1, . . . , 5} and transformations a = (3, 4), b = (1, 2, 3)(4, 5).
Let A′ have states {1, . . . , 10} and transformations a′ = (1, 2)(6, 8)(7, 9) and
b′ = (2, 6, 4, 5, 3, 7)(8, 10, 9).
The transition group G of A is S5 , and the transition group G′ of A′ is
a primitive subgroup of S10 that is isomorphic to S5 . Furthermore, the map
w 7→ w′ is an isomorphism of G and G′ . Hence A and A′ are similar. This pair
of DFAs has other interesting properties; we will revisit them in Example 21.
Notice that similarity of DFAs is a very fragile property; if we simply switch
the roles of a′ and b′ in A′ , giving a = (3, 4) and a′ = (2, 6, 4, 5, 3, 7)(8, 10, 9),
then A and A′ are no longer similar. Indeed, after the switch, wee see that
w 7→ w′ sends an element of order two to an element of order six, which means
it cannot be an isomorphism of G and G′ .

Dissimilar permutation DFAs have the following nice property.
Proposition 8. If A and A′ are dissimilar permutation DFAs, then at least one
of the following statements holds:
1. Rπ ′ is a non-trivial normal subgroup of G′ .
2. Cπ is a non-trivial normal subgroup of G.
If A and A′ are strongly dissimilar, then both hold.
Proof. Recall that R = ker π and C = ker π ′ ; these are normal subgroups of G× .
Since π and π ′ are surjective, Rπ ′ is a normal subgroup of G′ and Cπ is a normal
subgroup of G.
– We have ker π = {(w, w′ ) ∈ G× : w = ε}, so Rπ ′ = {w′ ∈ G′ : w = ε} and
similarly Cπ = {w ∈ G : w′ = ε′ }.
– If Rπ ′ is trivial, then whenever w = ε we have w′ = ε′ , and so R = ker π =
{(ε, ε′ )} is trivial; hence π is injective.
– Similarly, if Cπ is trivial, then C = ker π ′ is trivial, and thus π ′ is injective.
Thus we see that if A and A′ are dissimilar, then π and π ′ cannot both be
injective, and so Rπ ′ and Cπ cannot both be trivial. Furthermore, if A and A′
are strongly dissimilar, then neither π nor π ′ can be injective, and so neither
Rπ ′ nor Cπ can be trivial.
⊓
⊔
This leads to a useful theorem:
Theorem 2. Let A and A′ be dissimilar permutation DFAs with |Q|, |Q′ | ≥ 3.
1. Suppose G and G′ are transitive. If all non-trivial normal subgroups of G
and of G′ are transitive, then A × A′ is accessible.
2. Suppose G and G′ are primitive. If all non-trivial normal subgroups of G
and of G′ are primitive, then A × A′ is uniformly Boolean minimal.
35

Proof. By Proposition 8, since A and A′ are dissimilar, one of Rπ ′ or Cπ is a
non-trivial normal subgroup. Suppose that Cπ ≤ G is non-trivial; the other case
is symmetric.
(1): Since all non-trivial normal subgroups of G are transitive, Cπ is transitive. Hence Cq′ π is transitive for all q ′ ∈ Q, since Cq′ π ≥ Cπ. Since G′ is
transitive, we see that condition (3) of Lemma 2 holds. Thus A × A′ is accessible.
(2): Since all non-trivial normal subgroups of G are primitive, Cπ is primitive. Hence Cp′ ,q′ π is primitive for all p′ , q ′ ∈ Q, since Cp′ ,q′ π ≥ Cπ. Since G′ is
primitive, we see that A and A′ meet the conditions of Lemma 3. Thus A × A′
is uniformly Boolean minimal.
⊓
⊔
The power of Theorem 2 comes from the fact that several interesting classes of
groups have the property that all non-trivial normal subgroups are transitive or
primitive. The next corollary gives examples of when Theorem 2 can be applied.
Corollary 3. Let A and A′ be dissimilar permutation DFAs with |Q|, |Q′ | ≥ 3.
1. Suppose G and G′ are transitive.
(a) If G and G′ are transitive simple groups, then A × A′ is accessible.
(b) If G and G′ are primitive groups, then A × A′ is accessible.
2. Suppose G and G′ are primitive.
(a) If G and G′ are primitive simple groups, then A×A′ is uniformly Boolean
minimal.
(b) If G is SQ or AQ , and G′ is SQ′ or AQ′ , and we have (|Q|, |Q′ |) 6∈
{(3, 4), (4, 3), (4, 4)}, then A × A′ is uniformly Boolean minimal.
(c) If G and G′ are 2-transitive groups which are not of affine type, then
A × A′ is uniformly Boolean minimal.
Before proving this, we will explain what we mean by “affine type”. The notion
of “affine type” comes from the O’Nan-Scott theorem [12, Theorem 4.1A], a
structure theorem for primitive groups. The O’Nan-Scott theorem divides the
primitive groups into different types based on their socle. The socle of a group
G is the subgroup generated by all the minimal normal subgroups of G, that is,
the normal subgroups N of G for which there does not exist a non-trivial normal
subgroup N ′ of G with N ′ ⊆ N .
A group is abelian if its binary operation is commutative. A primitive group
with an abelian socle is necessarily of affine type, which means it is a permutation
group of degree pd for p prime and d ≥ 1, and is isomorphic to a subgroup of the
affine group AGL(d, p). This is a group of permutations of the set Fdp , where Fp is
the finite field with p elements; it consists of all maps of the form (γ1 , . . . , γd ) 7→
(αγ1 + β, . . . , αγd + β), where α, β, γ1 , . . . , γd ∈ Fp . After this proof, we will show
that there exist DFAs A and A′ whose transition groups are 2-transitive groups
of affine type, such that A × A′ is not uniformly Boolean minimal. Hence in
the statement of Corollary 3 (2c), excluding 2-transitive groups of affine type
is necessary. We remark that A3 , S3 , A4 and S4 happen to be groups of affine
type; we will see in the proof that this is not true for symmetric and alternating
groups of larger degree.
36

Proof. (1a): Recall that a group is simple if it has no non-trivial proper normal
subgroups. Hence if G is a transitive simple group, then the only non-trivial
normal subgroup of G is G itself. Similarly, the only non-trivial normal subgroup
of G′ is G′ itself. Thus the conditions of Theorem 2 hold.
(1b) Suppose G and G′ are primitive. It is an easy exercise in group theory
to show that all non-trivial normal subgroups of a primitive group are transitive
(e.g., see [12, Theorem 1.6A]). Thus the conditions of Theorem 2 hold in this
case.
(2a): Since G is a primitive simple group, then the only non-trivial normal
subgroup of G is G itself, and similarly for G′ . Thus the conditions of Theorem
2 hold.
(2b): First suppose |Q| 6= 4 and |Q′ | 6= 4. It is well-known that An is simple
for n 6= 4 (e.g., see [12, Corollary 3.3A]). Thus AQ and AQ′ are primitive simple
groups. So if G = AQ and G′ = AQ′ , this case follows from (2a).
Now, consider the symmetric groups. It is well-known that for n 6= 4, the
only non-trivial normal subgroups of Sn are An and Sn .
To see this, let N be a non-trivial normal subgroup of Sn . If An ≤ N , we
claim that either N = An or N = Sn . Indeed, if N properly contains An , then
it contains some permutation p that cannot be written as a product of an even
number of 2-cycles. But every permutation can be written as a product of 2cycles, so p can be written as a product of an odd number of 2-cycles. Thus for
each 2-cycle (i, j), we have (i, j)p ∈ An ≤ N . So N contains (i, j)pp−1 = (i, j);
since N contains all 2-cycles, we must have N = Sn .
If N ≤ An , consider ghg −1 for g ∈ An and h ∈ N . Since g, h and g −1 are
all in An , each can be written a product of an even number of 2-cycles, and
thus ghg −1 can be written this way as well. So N is also a non-trivial normal
subgroup of An ; but An is simple for n 6= 4, so we must have N = An .
Thus a non-trivial normal subgroup is either Sn or An . both of which are
′
)}, Theorem 2 applies
primitive. Thus if (G, G′ ) ∈ {(AQ , SQ′ ), (SQ , AQ′ ), (SQ , SQ
and gives the result. Note we have also shown that for n ≥ 5, the alternating
group An is the unique minimal normal subgroup of Sn and An . Thus the socle
of Sn and An is non-abelian, which shows that Sn and An are not of affine type
when n ≥ 5.
Now, suppose |Q| = 4 or |Q′ | = 4 and (|Q|, |Q′ |) 6∈ {(3, 4), (4, 3), (4, 4)}. Then
|Q| ≥ 5 or |Q′ | ≥ 5. Assume without loss of generality that |Q| = 4 and |Q′ | ≥ 5;
the other case is symmetric. Consider the normal subgroup Rπ ′ of G′ . If Rπ ′ is
trivial, then as we argued in the proof of Proposition 8, the map π : G× → G
must be injective. Since G is either A4 or S4 , this means |G× | ≤ |S4 | = 24. But
the map π ′ : G× → G′ is surjective, and G is either AQ′ or SQ′ for |Q′ | ≥ 5. This
means |G× | ≥ |A5 | = 60. So we have 60 ≤ 24, which is a contradiction. Thus
Rπ ′ cannot be trivial. So Rπ ′ is a non-trivial normal subgroup of G′ , and thus
it is primitive, since G′ is SQ′ or AQ′ and |Q′ | ≥ 5. Thus the arguments in the
proof of Theorem 2 apply and A × A′ is uniformly Boolean minimal.
(2c): The results from permutation group theory that we use for this case
are somewhat more advanced. We will need the fact that a 2-transitive group
37

has a unique minimal normal subgroup; this follows from two theorems in [12]
(Theorem 4.1B and Theorem 4.3B), or alternatively is stated as a single result
in [10] (Proposition 5.2). The other fact we need is that if the socle of a 2transitive group is non-abelian, it is necessarily primitive [12, Theorem 7.2E].
Now, suppose G is 2-transitive. The socle of G is the subgroup generated by
all the minimal normal subgroups; but G has a unique minimal normal subgroup
N , so the socle of G is just equal to N . If N is abelian, then G is of affine
type. Thus we may assume the socle N is non-abelian; then it follows that N is
primitive. Since N is the unique minimal normal subgroup of G, every non-trivial
normal subgroup of G contains N , and thus is primitive. Similarly, every nontrivial normal subgroup of G′ is primitive. It follows that Theorem 2 applies. ⊓
⊔
4.5

Affine Groups

We now construct an infinite family of pairs of dissimilar permutation DFAs
which have 2-transitive transition groups of affine type, and are not uniformly
boolean minimal. The details of the construction require some knowledge of
finite fields. We will first give the construction in full generality, and then use
the construction to produce an explicit pair of 8-state DFAs.
Example 17. For k ≥ 0, let F2k denote the finite field of order 2k . For α, β, ξ ∈
F2k with α 6= 0, define tα,β : F2k → F2k to be the map ξ 7→ αξ + β. The
set of all such maps forms a group of permutations of F2k , which is called the
1-dimensional affine group on F2k and is denoted AGL(1, 2k ). Multiplication
(that is, composition of maps) in the affine group is given by the rule
tα,β tγ,ξ = tαγ,βγ+ξ .
It is an easy but somewhat tedious exercise to show that the affine group is
2-transitive. In [12, Chapter 4] it is proved that the affine group has an abelian
socle.
Recall that the multiplicative group of a finite field is cyclic. Let x be a
generator for the multiplicative group of F2k . We claim that the elements tx,0
and t1,1 generate AGL(1, 2k ). This is once again an easy but tedious exercise,
so we omit a proof.
An element of AGL(1, 2k ) of the form t1,β for some β ∈ F2k is called a
translation. The translations form a subgroup of AGL(1, 2k ), which we call T .
We claim that the subgroup of translations T is imprimitive and contains a block
B of size 2k−1 .
To see this, recall that F2k is a k-dimensional vector space over F2 . Pick
k − 1 non-zero elements of F2k and let B be the subspace spanned by them. Now
consider Bt1,β for β ∈ F2k .
– If β ∈ B, then α+β ∈ B for all α ∈ B, since B is a subspace; thus Bt1,β = B.
– If β 6∈ B, then for all α ∈ B we have α + β 6∈ B. Indeed, if α + β was in B
then (α + β) − α = β would be in B, since B is a subspace.
– Thus if β 6∈ B, then Bt1,β ∩ B = ∅.
38

And so, we see that B is indeed a block for T .
Consider the subgroup A of AGL(1, 2k ) × AGL(1, 2k ) generated by the elements a = (tx,0 , tx,0 ), b = (t1,1 , t1,0 ) and c = (t1,0 , t1,1 ). We claim that every
element (tα,β , tγ,ξ ) of A has the property that α = γ. For simplicity, we will call
elements with this property balanced.
Certainly the elements a, b and c are balanced, and so is the identity element
(t1,0 , t1,0 ). We will show that multiplying a balanced element on the right by a,
b or c results in a balanced element. Indeed, first observe that tα,β tx,0 = tαx,βx
and tα,β t1,1 = tα,β+1 . Thus if we take an arbitrary balanced element (tα,β , tα,γ ),
then we have:
(tα,β , tα,γ )a = (tα,β tx,0 , tα,γ tx,0 ) = (tαx,βx , tαx,γx ).
(tα,β , tα,γ )b = (tα,β t1,1 , tα,γ t1,0 ) = (tα,β+1 , tα,γ ).
(tα,β , tα,γ )c = (tα,β t1,0 , tα,γ t1,1 ) = (tα,β , tα,γ+1 ).
Since a, b and c and the identity are balanced, and multiplying a balanced
element by a, b or c results in a balanced element, it follows the group ha, b, ci = A
consists solely of balanced elements.
Next, let B = F2k \B and consider the set X = (B ×B)∪(B ×B) ⊆ F2k ×F2k .
Notice that (0, 0), (1, 1) ∈ F2k × F2k both lie in X. We claim that elements of A
cannot distinguish (0, 0) and (1, 1) with respect to X, that is, for all g ∈ A we
have (0, 0)g ∈ X ⇔ (1, 1)g ∈ X.
– To see this, consider an arbitrary element g = (tα,β , tα,γ ) of A.
– We have 0tα,β = β and 1tα,β = α + β. It follows that (0, 0)g = (β, γ) and
(1, 1)g = (α + β, α + γ) = (βt1,α , γt1,α ).
– Since B is a block for the subgroup of translations T , we either have Bt1,α =
B or Bt1,α ∩ B = ∅.
– But B has size 2k−1 , which is exactly half the size of F2k , so if Bt1,α ∩ B = ∅
then Bt1,α = B.
It follows that if (β, γ) is in B × B or B × B (that is, (β, γ) is in X) then
(βt1,α , γt1,α ) is also in B × B or B × B (and thus in X).
Likewise, if (β, γ) is not in X, then it is either in B × B or B × B, and it
follows (βt1,α , γt1,α ) is not in X. Thus (0, 0)g ∈ X ⇔ (1, 1)g ∈ X for all g ∈ A.
Finally, for each k ≥ 1, we construct a pair of DFAs over the alphabet {a, b, c}
with 2k states each, which both have AGL(1, 2k ) as their transition group, but
do not have a uniformly boolean minimal direct product.
We define a DFA A as follows:
– The state set is F2k , the initial state is 0, and the final state set is B.
– The transformations are a = tx,0 , b = t1,1 and c = t1,0 .
We define A′ in the same way as A, except the roles of b and c are swapped:
– The transformations are a′ = tx,0 , b′ = t1,0 and c′ = t1,1 .
39

Since tx,0 and t1,1 generate AGL(1, 2k ), it is clear that both DFAs have AGL(1, 2k )
as their transition group.
Now consider A × A′ . Let ◦ be the “complement of symmetric difference”
operation, so that B ◦ B = (B × B) ∪ (B × B). Observe that the transition group
of A × A′ is simply the group A. Thus the states (0, 0) and (1, 1) of A × A′
are not distinguishable by B ◦ B. Hence (A × A′ )(B ◦ B) is not minimal, and it
follows that A × A′ is not uniformly boolean minimal.

Example 18. We now carry out the construction of Example 17 for k = 3, 2k = 8.
First, we must construct the finite field F8 . Let F2 = {0, 1} denote the ring of
integers modulo two. We define F8 to be the quotient ring F2 [x]/hx3 + x + 1i.
This ring consists of polynomials of the form {a + bx + cx2 : a, b, c ∈ F2 }.
Addition and multiplication work as usual for polynomials, except when multiplying, any terms of degree 3 or higher are reduced by repeatedly applying
the rule x3 = x + 1. Note also that since the coefficients of the polynomials
are in F2 , we have 2f (x) = 0 for all polynomials f (x). For example, we have
(x2 + x + 1) + (x2 + 1) = x. Applying these facts, we see that:
x3 = x + 1,

x4 = x2 + x,

x5 = x3 + x2 = x2 + x + 1,

x6 = x3 + x2 + x = x2 + x + x + 1 = x2 + 1,

x7 = x3 + x = x + 1 + x = 1.

These calculations show that every non-zero element of F8 can be written as
a power of the monomial x; in particular, 1 can be written as a power of x,
and thus x is invertible. Hence F8 is indeed a field and x is a generator of the
multiplicative group of F8 .
Next, we explicitly write out the permutations tx,0 and t1,1 in cycle notation:
tx,0 = (x, x2 , x3 , x4 , x5 , x6 , x7 ) = (x, x2 , x + 1, x2 + x, x2 + x + 1, x2 + 1, 1).
t1,1 = (0, 1)(x, x+1)(x2 , x2 +1)(x2 +x, x2 +x+1) = (0, x7 )(x, x3 )(x2 , x6 )(x4 , x5 ).
Finally, we need to find a block B for the subgroup of translations of AGL(1, 8).
The construction tells us to pick two non-zero elements of F8 and let B be the
subspace spanned by them. If we take 1 and x, we get B = {0, 1, x, x + 1}.
We now have all the information we need to construct A and A′ . A state
diagram for A is shown in Figure 5, with the self-loops on c omitted. One may
verify computationally that A × A′ is not minimal when it is assigned the final

state set (B × B) ∪ (B × B).
For k = 1, we get DFAs A, A′ and A × A′ that are isomorphic to the
DFAs of Example 11. For k = 2, it happens that AGL(1, 4) is isomorphic to
the alternating group A4 . Hence the k = 2 case gives an example of dissimilar
DFAs that are not uniformly boolean minimal, and have alternating groups as
their transition groups. As Corollary 3 shows, this example does not generalize
to alternating groups of higher degree. The DFA A of Example 9 is isomorphic
to the DFA A produced by the construction of Example 17 with k = 2.
The construction of Example 17 also shows that condition (1) of Proposition
7 is not sufficient for uniform boolean minimality.
40

a

b
b

0

x7
a

a

x

x6

a

b
x2

b b

b

a

a
x3

x5
a

b
x4

a, b

Fig. 5. DFA A of Example 18. Each state also has a self-loop on letter c; these transitions are omitted from the diagram. The final state set is B = {0, x7 = 1, x, x3 = x+1},
the block of the subgroup of translations of AGL(1, 8) that was found in Example 18.

Example 19. The DFAs A and A′ constructed in Example 17 are not uniformly
boolean minimal. However, we claim the subgroups Rα π ′ ≤ G′ and Cα π ≤ G are
primitive for all α ∈ F2k , and thus A and A′ meet condition (1) of Proposition
7. In fact, the groups Rα π ′ and Cα π are equal to AGL(1, 2k ). First, we show
that R0 π ′ and C0 π are equal to AGL(1, 2k ). Consider (a, a′ ) = (tx,0 , tx,0 ).
– Since tx,0 fixes 0, it follows that (a, a′ ) ∈ R0 and (a, a′ ) ∈ C0 .
Thus a′ = tx,0 ∈ R0 π ′ and a = tx,0 ∈ C0 π.
– Since (b, b′ ) = (t1,1 , t1,0 ) and b′ = t1,0 fixes 0, we see that (b, b′ ) ∈ C0 .
Thus b = t1,1 ∈ C0 π.
– Similarly, since (c, c′ ) = (t1,0 , t1,1 ), we see that (c, c′ ) ∈ R0 .
Thus c′ = t1,1 ∈ R0 π ′ .
Since tx,0 and t1,1 generate AGL(1, 2k ), and these elements are in R0 π ′ and C0 π,
it follows R0 π ′ and C0 π are equal to AGL(1, 2k ) and thus are primitive.
To show that Rα π ′ and Cα π are primitive for all α 6= 0, we prove a general
fact about single row and column stabilizers: if Cp′ π ≤ G is primitive for some
p′ ∈ Q′ and G′ is transitive, then Cq′ π is primitive for all q ′ ∈ Q′ (and similarly
for single row stabilizers).
To see this, choose w′ ∈ G′ such that p′ w′ = q ′ .
Let B be a block for Cq′ π. We claim Bw−1 is a block for Cp′ π.
To see this, choose x ∈ Cp′ π and consider Bw−1 x ∩ Bw−1 .
If Bw−1 x ∩ Bw−1 6= ∅, then Bw−1 xw ∩ B 6= ∅.
Now, for all x ∈ Cp′ π, we have p′ x′ = p′ by definition.
It follows q ′ (w′ )−1 x′ w′ = p′ x′ w′ = p′ w′ = q ′ . Since (w′ )−1 x′ w′ fixes q ′ , we
have w−1 xw ∈ Cq′ π.
– Since B is a block for Cq′ π and Bw−1 xw ∩ B 6= ∅, we have Bw−1 xw = B.
– Hence Bw−1 x = Bw−1 , which proves Bw−1 is a block for Cp′ π.

–
–
–
–
–
–

41

It follows that if B is a block for Cq′ π, it must be a trivial block; otherwise Bw−1
is a non-trivial block for the primitive group Cp′ π, which is a contradiction.
Thus Cα π is primitive for all α ∈ F2k , and symmetrically we see that Rα π ′
is primitive for all α ∈ F2k . This shows that A and A′ satisfy condition (1) of
Proposition 7, yet A × A′ is not uniformly boolean minimal.

We can also use DFAs derived from affine groups to show that the conditions
of Lemma 3 are not necessary for uniform boolean minimality.
Example 20. As in Example 18, we define two DFAs A and A′ that have transition group AGL(1, 8). However, this time the direct product of the DFAs will
be uniformly boolean minimal. We define A as follows (leaving the final state
set unspecified).
– The state set is F8 , constructed as in Example 18, and the initial state is 0.
– The transformations are a = tx,0 and b = t1,1 .
′
Define A′ to have the same states as A and transformations a′ = t−1
x,0 , b = t1,1 .
′
Since A and A only have 8 states each, we were able to verify computationally that A × A′ is uniformly boolean minimal by a brute force approach. We
computed A × A′ , and for each pair of sets ∅ ( S ( Q and ∅ ( S ′ ( Q′ , we
checked the minimality of (A × A′ )(X) for all (S, S ′ )-compatible sets X.
We have also verified computationally that R0,1 π ′ and C0,1 π are imprimitive,
and hence A and A′ do not meet the conditions of Lemma 3. We verified this
by using the cycle notation representation we found for tx,0 and t1,1 to explicitly
construct the transition group G× of A × A′ in GAP. Then we computed the
setwise stabilizer R0,1 of {0, 1} × F8 (the rows indexed by 0 and 1), and the
setwise stabilizer C0,1 of F8 × {0, 1} (the columns indexed by 0 and 1). Next,
we computed R0,1 π ′ ≤ G′ and C0,1 π ≤ G. These groups turned out to both be
equal to T , the subgroup of translations in AGL(1, 8). We saw earlier than T is
imprimitive.


We suspect that if this construction is generalized to AGL(1, 2k ), the resulting DFAs will have the same property of being uniformly boolean minimal but
having R0,1 π ′ and C0,1 π imprimitive. However, we were unable to prove this.
4.6

Similar DFAs

To close out Section 4, we consider what happens when the DFAs A and A′
are similar. We have not investigated this case very deeply. In some ways, it
seems much more difficult than the dissimilar case. Particularly, most of our
results rely on the projections of various kinds of row and column stabilizers
being transitive or primitive. For similar DFAs, the projections of the full row
and column stabilizers Cπ and Rπ ′ are both trivial. Hence there is no guarantee
that other types of stabilizers such as Rq π ′ or Cp′ ,q′ π have useful properties, or
even that they are non-trivial, and so we cannot necessarily use these groups to
our advantage.
42

On the other hand, similarity imposes the very strong condition that the
groups G, G′ and G× are all isomorphic. It may be possible to exploit this to
prove some interesting things in the similar case.
It is not difficult to prove that if A and A′ are isomorphic as DFAs, then G×
is necessarily intransitive, so the case of isomorphic similar DFAs is uninteresting
for our purposes. We give two examples demonstrating what can happen with
non-isomorphic similar DFAs.
Example 21. Recall that in Example 16, we constructed two similar DFAs that
are of different sizes (and hence are non-isomorphic) and have primitive transition groups.
– A has states {1, . . . , 5} and transformations a = (3, 4), b = (1, 2, 3)(4, 5).
– A′ has states {1, . . . , 10} and transformations a′ = (1, 2)(6, 8)(7, 9) and b′ =
(2, 6, 4, 5, 3, 7)(8, 10, 9).
We have verified computationally that A × A′ has an intransitive transition
group, and so is not accessible. Thus even if non-isomorphic similar DFAs have
primitive transition groups, their direct product might have an intransitive transition group (compare this with Corollary 3 for dissimilar DFAs).
Note that in Example 16, we also showed that by simply swapping the roles
of a′ and b′ in A′ , the two DFAs A and A′ become dissimilar. Furthermore, A
has the symmetric group S5 as its transition group. Thus by Corollary 3, the
two DFAs actually become uniformly boolean minimal if we swap the roles of a′
and b′ .

Example 22. There is a primitive subgroup of S6 that is isomorphic to S5 . Using
GAP, we can obtain an explicit isomorphism between S5 and this subgroup, just
as we did in Example 16.
gap> IsomorphismGroups(SymmetricGroup(5),PrimitiveGroup(6,2));
[ (3,4), (1,2,3)(4,5) ] -> [ (1,2)(3,4)(5,6), (1,2,3,5,4,6) ]
We then use this isomorphism to construct similar DFAs:
– A has states {1, . . . , 5} and transformations a = (3, 4) and b = (1, 2, 3)(4, 5).
– A′ has states {1, . . . , 6} and transformations a′ = (1, 2)(3, 4)(5, 6) and b′ =
(1, 2, 3, 4, 5, 6).
Unlike the DFAs of Example 21, here we verified computationally that A ×
A′ actually has a transitive transition group. Hence a direct product of nonisomorphic similar DFAs with primitive transition groups may or may not be
accessible.
Note that A × A′ is not uniformly boolean minimal. For example, we have
verified computationally that (A×A′ )(X) is not minimal for X = {1}×{1, 3, 5}.
We have not found an example of two similar DFAs that are uniformly boolean
minimal, but we also have not proved that no such example exists.

43

5

Conclusion

We summarize the major results proved in Section 4.
Theorem 1 gives necessary and sufficient conditions for a pair of regular
languages (L, L′ ) to have maximal boolean complexity, with the requirement
that these languages are recognized by permutation DFAs A and A′ with exactly
one final state. In this special case, it turns out that (L, L′ ) is uniformly boolean
minimal if and only if A × A′ is accessible. This gives a partial characterization
of witnesses for the state complexity of proper binary boolean operations.
We have several results which may help to determine whether A × A′ is
accessible. Lemma 2 gives group-theoretic conditions for accessibility, while
Proposition 6 gives a useful graph-theoretic condition.
Theorem 2 gives a particularly useful group-theoretic condition for accessibility of A × A′ , as well as a similar condition for uniform boolean minimality.
The power of this theorem is demonstrated by Corollary 3, which gives several
classes of groups where the condition of Theorem 2 holds. If one can show that
the transition group A or of A′ lies in one of these classes, one immediately
gets useful information about A × A′ . Corollary 3 is also useful for constructing
examples of DFAs whose direct product is accessible or uniformly boolean minimal: one may pick a pair of groups from the classes mentioned in the corollary,
and use them as the transition groups of a pair of DFAs.
Lemma 3 gives some sufficient conditions for uniform boolean minimality
of permutation DFAs. The conditions are stronger than those of Theorem 2,
but more difficult to verify. Unfortunately, Example 20 shows that these conditions are not necessary. Necessary and sufficient conditions for uniform boolean
minimality are still unknown.
Proposition 7 gives a necessary and sufficient condition (1) for a property
that is slightly weaker than uniform boolean minimality to hold (in permutation
DFAs). Specifically, condition (1) of Proposition 7 does not guarantee minimality
for final state sets corresponding to the symmetric difference operation or its
complement.
Unfortunately, Example 19 shows that condition (1) of Proposition 7 is not
sufficient for uniform boolean minimality. This means a precise characterization of uniform boolean minimality lies strictly between the conditions given by
Lemma 3 and Proposition 7.
We state some unsolved problems and potential new directions of research
arising from our work in this paper.
– Find necessary and sufficient conditions for A × A′ to be uniform boolean
minimal. Even in the special case of permutation DFAs, we were unable to
resolve this.
– Find more classes of groups where the hypotheses of Theorem 2 hold, thus
extending the reach of Corollary 3.
– Find an example of two similar DFAs that are uniformly boolean minimal, or
prove that no such DFAs exist. Even pairs of similar DFAs with an accessible
direct product seem to be rare; one such pair is given in Example 22.
44

– Prove anything interesting about accessibility and/or uniform boolean minimality of direct products of non-isomorphic similar DFAs.
– Investigate uniform boolean minimality with respect to “unrestricted state
complexity” (see the last two paragraphs of Section 2).
– Investigate uniform boolean minimality for DFAs that do not contain “interesting” subgroups of permutations. That is, let us say the transition group
of a DFA is “interesting” if it satisfies the hypotheses of any of our major
results. Although we stated our results exclusively for permutation DFAs,
they hold more generally for DFAs whose transition monoids contain an “interesting” subgroup of permutations. However, many DFAs have transition
monoids which do not contain “interesting” subgroups; for example, DFAs of
star-free languages have transition monoids with no non-trivial subgroups.
In these cases, what can we say about uniform boolean minimality, or even
accessibility of direct products?
– Look for necessary and/or sufficient conditions characterizing state complexity witnesses for operations on regular languages other than boolean
operations (e.g., concatenation, star, reverse). As these problems could be
extremely difficult, it may be useful to start with the special case of group
languages or some other subclass of the regular languages.
Acknowledgements
I thank Jason Bell and Janusz Brzozowski for careful proofreading and helpful
comments. The computer algebra system GAP [14] was invaluable for this research; I cannot overstate its importance in obtaining these results. In particular,
I thank the authors of the Automata GAP package [11] and all contributors to
GAP’s library of primitive groups.
Funding: This work was supported by the Natural Sciences and Engineering
Research Council of Canada under grant No. OGP0000871.

References
1. Almeida, J., Rodaro, E.: Semisimple synchronizing automata and the WedderburnArtin theory. Int. J. Found. Comput. Sc. 27(02), 127–145 (2016)
2. Araújo, J., Cameron, P.J., Steinberg, B.: Between primitive and 2-transitive: synchronization and its friends. https://arxiv.org/abs/1511.03184 (Nov 2015)
3. Bell, J., Brzozowski, J., Moreira, N., Reis, R.: Symmetric groups and quotient
complexity of boolean operations. In: Esparza, J., et al. (eds.) ICALP 2014. LNCS,
vol. 8573, pp. 1–12. Springer (2014)
4. Bosma, W., Cannon, J., Playoust, C.: The Magma algebra system I: The user
language. J. Symbolic Comput. 24(3–4), 235–265 (1997)
5. Brzozowski, J.: Quotient complexity of regular languages. J. Autom. Lang. Comb.
15(1/2), 71–89 (2010)
6. Brzozowski, J.: In search of most complex regular languages. Int. J. Found. Comput. Sc. 24(06), 691–708 (2013)

45

7. Brzozowski, J.: Unrestricted state complexity of binary operations on regular languages. In: Câmpeanu, C., Manea, F., Shallit, J. (eds.) DCFS 2016. LNCS, vol.
9777, pp. 60–72. Springer (2016)
8. Brzozowski, J., Jirásková, G., Li, B.: Quotient complexity of ideal languages. Theoret. Comput. Sci. 470, 36–52 (2013)
9. Brzozowski, J., Liu, B.: Quotient complexity of star-free languages. Int. J. Found.
Comput. Sc. 23(06), 1261–1276 (2012)
10. Cameron, P.J.: Finite permutation groups and finite simple groups. Bull. London
Math. Soc 13(1), 1–22 (1981)
11. Delgado, M., Linton, S., Morais, J.: Automata – a GAP package, Version 1.13.
http://cmup.fc.up.pt/cmup/mdelgado/automata/ (19 November 2011)
12. Dixon, J.D., Mortimer, B.: Permutation groups. Springer (1996)
13. Ésik, Z., Gao, Y., Liu, G., Yu, S.: Estimation of state complexity of combined
operations. Theoret. Comput. Sci. 410(35), 3272–3280 (2009)
14. The GAP Group: GAP – Groups, Algorithms, and Programming, Version 4.8.6
(2016), http://www.gap-system.org
15. Maslov, A.N.: Estimates of the number of states of finite automata. Dokl. Akad.
Nauk SSSR 194, 1266–1268 (Russian) (1970), English translation: Soviet Math.
Dokl. 11(1970) 1373–1375
16. Restivo, A., Vaglica, R.: Extremal minimality conditions on automata. Theor.
Comput. Sci. 440–441, 73–84 (2012)
17. Restivo, A., Vaglica, R.: A graph theoretic approach to automata minimality. Theoret. Comput. Sci. 429, 282–291 (2012)
18. Salomaa, A., Salomaa, K., Yu, S.: State complexity of combined operations. Theoret. Comput. Sci. 383(2), 140–152 (2007)
19. Salomaa, A., Wood, D., Yu, S.: On the state complexity of reversals of regular
languages. Theoret. Comput. Sci. 320(2), 315–329 (2004)
20. Steinberg, B.: A theory of transformation monoids: combinatorics and representation theory. https://arxiv.org/abs/1004.2982 (Apr 2010)
21. Yu, S., Zhuang, Q., Salomaa, K.: The state complexities of some basic operations
on regular languages. Theor. Comput. Sci. 125(2), 315–328 (1994)

46

