Title: Primitivity, Uniform Minimality and State Complexity of Boolean Operations,
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, non-trivial 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.