The The methods for alleviating the state explosion problem in model checking can be classified coarsely into symbolic methods and abstraction methods [6] . By symbolic methods we understand the use of succinct data structures and symbolic algorithms which help keep state explosion under control by compressing information, using, e.g., binary decision diagrams or efficient SAT procedures. Abstraction methods in contrast attempt to reduce the size of the state space by employing knowledge about the system and the specification in order to model only relevant features in the Kripke structure. An abstraction function associates a Kripke structure Ã with an abstract Kripke structure Ã such that two properties hold: Preservation. Ã preserves all behaviors of Ã. Preservation ensures that every universal specification which is true in Ã is also true in Ã. The converse implication, however, will not hold in general: a universal property which is false in Ã may still be true in Ã. In this case, the counterexample obtained over Ã cannot be reconstructed for the concrete Kripke structure Ã, and is called a spurious counterexample [10] , or a false negative. An important example of abstraction is existential abstraction [11] where the abstract states are essentially taken to be equivalence classes of concrete states; a transition between two abstract states holds if there was a transition between any two concrete member states in the corresponding equivalence classes. In certain cases, the user knowledge about the system will be sufficient to allow manual determination of a good abstraction function. In general, however, finding abstraction functions gives rise to the following dichotomy: If Ã is too small, then spurious counterexamples are likely to occur. If Ã is too large, then verification remains infeasible. Counterexample-Guided Abstraction Refinement (CEGAR) is a natural approach to resolve this situation by using an adaptive algorithm which gradually improves an abstraction function by analysing spurious counterexamples. (i) Initialization. Generate an initial abstraction function. (ii) Model Checking. Verify the abstract model. If verification is successful, the specification is correct, and the algorithm terminates successfully. Otherwise, generate a counterexample Ì on the abstract model. (iii) Sanity Check. Determine, if the abstract counterexample Ì is spurious. If a concrete counterexample
Our approach for alphabet refinement is similar in spirit to counterexample-guided abstraction refinement (CEGAR) REF .
Counterexample-guided abstraction refinement
In Computer Aided Verification
Computer Science