|
Abstract : |
Abstract. This work presents a minimization algorithm. The algorithm receives a Kripke structure M and returns the smallest structure that is simulation equivalent to M. The simulation equivalence relation is weaker than bisimulation but stronger than the simulation preorder. It strongly preserves ACTL and LTL (as sub-logics of ACTL We show that every structure M has a unique up to isomorphism reduced structure that is simulation equivalent to M and smallest in size. We give a Minimizing Algorithm that constructs the reduced structure. It first constructs the quotient structure for M, then eliminates transitions to little brothers and finally deletes unreachable states. The first step has maximal space requirements since it is based on the simulation preorder over M. To reduce these requirements we suggest the Partitioning Algorithm which constructs the quotient structure for M without ever building the simulation preorder. The Partitioning Algorithm has a better space complexity but might have worse time complexity., |
