Paper Details

A Hierarchy of Polynomial-Time Computable Simulations for Automata
Kousha Etessami

We define and provide algorithms for computing a natural hierarchy of simulation relations on the state-spaces of ordinary transition systems, finite automata, and Büchi automata. These simulations enrich ordinary simulation and can be used to obtain greater reduction in the size of automata by computing the automaton quotient with respect to their underlying equivalence. State reduction for Büchi automata is important for making explicit-state model checking run faster ([EH2000,SB00,EWS01]).