A Hierarchy Of Polynomial-Time Computable Simulations For Automata /

We define and provide algorithms for computing a natural hierarchy of simulation relations on the state-space of ordinary transition systems, finite automata, and Buchi 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.