Since FSRAs are inherently nondeterministic (see the discussion of linearization below), their minimization is related to the problem of non-deterministic finite-state automata (NFA) minimization, which is known to be NP-hard.
6 while FSRA arc minimization is NP-hard, FSRA state minimization is different.