What does width $4$ permutation branching program correspond to?

$$L$$ can be computed by a family of programs over $$S_3$$ of polynomial length if and only if $$L$$ can be computed by a family of $$MOD3 ◦ MOD2$$ circuits of polynomial size.

$$L$$ can be computed by a family of programs over $$S_5$$ of polynomial length if and only if $$L$$ can be computed by a family of $$NC^1$$ circuits of polynomial size.

How about if $$L$$ can be computed by a family of programs over $$S_4$$?

• $S_4$ is solvable with composition factors $C_2$ (3 times) and $C_3$, thus you get again some low-depth combination of MOD2 and MOD3 gates. Jun 4 at 13:38
• Yeah, I seem to recall that b/c the (unique?) composition series is $1 \unlhd C_2 \times C_2 \unlhd A_4 \unlhd S_4$, that more specifically you get (perhaps a subfamily of) $MOD_2 \circ MOD_3 \circ MOD_2$ circuits. Jun 4 at 14:12
• How do composition factors relate to the family of programs and their circuits?
– Mr.
Jun 4 at 21:51
• I recommend to look in the following book. Howard Straubing. Finite automata, formal logic, and circuit complexity. Jun 12 at 12:25