Bounded model checking of infinite state systems: exploiting the automata hierarchy

We present a new approach to bounded model checking that extends current methods in two ways: firstly, instead of a reduction to propositional logic, we choose a more powerful, yet decidable target logic, namely Presburger arithmetic. Secondly, instead of unwinding temporal logic formulas, we unwind corresponding ω-automata. To this end, we employ a special technique for translating safety and liveness properties to ω-automata with corresponding acceptance conditions. This combination allows us to utilize bounded model checking techniques for the efficient verification of infinite state systems.