Compositionality is a fundamental notion in numerous fields of computer science. This principle can be summarised as follows: Every system should be designed by composing simple parts such that the meaning of the system can be deduced from the meaning of its parts, and how they are combined. For instance, this is a crucial aspect of modern software engineering: a program split into simple modules will be quicker to compile, easier to maintain and allowing concurrency.

A deterministic finite automaton (DFA) A is composite if its language L(A) can be decomposed into an intersection L(A1) ∩ L(A2) ∩ … ∩ L(Ak) 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 presentation, we focus on permutation DFAs, i.e., those for which the transition monoid is a group. By the use of structural criteria we are able to decide in NPTIME whether a permutation DFA is composite. Moreover, we investigate the class of commutative permutation DFAs for which we provide an NLOGSPACE procedure. Despite this low complexity (compared to the general case), we show that complex behaviours still arise in this class: we provide a family of commutative permutation DFAs each composite and requiring polynomially many factors with respect to its size.