  A deterministic finite automaton (DFA) is composite if its language can be
decomposed into an intersection of languages of smaller DFAs. Otherwise, A is
prime. This notion of primality was introduced by Kupferman and Mosheiff in
2013, and while they proved that we can decide whether a DFA is composite, the
precise complexity of this problem is still open, with a doubly-exponential gap
between the upper and lower bounds. In this work, we focus on permutation DFAs,
i.e., those for which the transition monoid is a group. We provide an NP
algorithm to decide whether a permutation DFA is composite, and show that the
difficulty of this problem comes from the number of non-accepting states of the
instance: we give a fixed-parameter tractable algorithm with the number of
rejecting states as the parameter. Moreover, we investigate the class of
commutative permutation DFAs. Their structural properties allow us to decide
compositionality in NLOGSPACE, and even in LOGSPACE if the alphabet size is
fixed. Despite this low complexity, we show that complex behaviors still arise
in this class: we provide a family of composite DFAs each requiring
polynomially many factors with respect to its size. We also consider the
variant of the problem that asks whether a DFA is k-factor composite, that is,
decomposable into k smaller DFAs, for some given integer k. We show that, for
commutative permutation DFAs, restricting the number of factors makes the
decision computationally harder, and yields a problem with tight bounds: it is
NP-complete. Finally, we show that in general, this problem is in PSPACE, and
it is in LOGSPACE for DFAs with a singleton alphabet.
