  Transition systems (TS) and Petri nets (PN) are important models of
computation ubiquitous in formal methods for modeling systems. An important
problem is how to extract from a given TS a PN whose reachability graph is
equivalent (with a suitable notion of equivalence) to the original TS.
  This paper addresses the decomposition of transition systems into
synchronizing state machines (SMs), which are a class of Petri nets where each
transition has one incoming and one outgoing arc and all markings have exactly
one token. This is an important case of the general problem of extracting a PN
from a TS. The decomposition is based on the theory of regions, and it is shown
that a property of regions called excitation-closure is a sufficient condition
to guarantee the equivalence between the original TS and a decomposition into
SMs.
  An efficient algorithm is provided which solves the problem by reducing its
critical steps to the maximal independent set problem (to compute a minimal set
of irredundant SMs) or to satisfiability (to merge the SMs). We report
experimental results that show a good trade-off between quality of results vs.
computation time.
