Synthesizing FSMs according to co-Büchi properties

Abstract. Computations are developed for the synthesis of an FSM embedded in a known larger system such that the overall behavior satisfies a co-Büchi specification. The procedures for this are very similar to those used for regular (non-omega) automata, except for a special final step in which a set of FSM solutions is represented as a SAT instance. Each satisfying assignment corresponds to an FSM solution. To reduce the SAT size, a preprocessing step splits a general solution automaton into a “path ” automaton and an “acceptance” automaton. Cycles in the path automaton graph are trimmed while maintaining the input-progressiveness property required for FSMs. Not all FSM solutions are represented by the SAT instance, since in theory there could be an infinite number. The computations have been implemented in the MVSIS environment and a few experiments have been done.