A Hierarchy of PolynomialTime Computable Simulations for Automata Kousha Etessami
We define and provide algorithms for computing a natural hierarchy of
simulation relations on the statespaces 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 explicitstate model checking run faster
([EH2000,SB00,EWS01]).

concur02@fi.muni.cz 