(C,D)∈Parr(D) =
!
C∈C
!
D∈DCarr(D) ≤ [as the blocks in DCare pairwise disjoint]
!
C∈C|!| ≤ [as |C| ≤ 2|Psim|]
2|Psim||!|.
Summing up, we have shown that the overall time-complexity of SimEquiv3is in O(|Psim||!|).
The space complexity is in O(|Σ| log(|Psim|) + |Psim| + |Psim|2+ |Psim||Σ|) = O(|Psim||Σ|) where:
– The pointers from any state s ∈ Σ to the block of the current partition that contains s is stored in O(|Σ| log(|Psim|)) space.
– The current partition is stored in O(|Psim|) space.
– The current relation is stored in O(|Psim|2) space.
– Each block of the current partition stores the corresponding remove set and the arrays BlockCount and RelCount, and these take O(|Psim||Σ|) space.
8 Experimental Evaluation
A pseudocode implementation of SimEquiv3 that shows how the data structures in Section 7.1 are ac-tually used is described in Figure 7. This code calls the SplittingProcedure in Figure 6. A prototype of this simulation equivalence algorithm has been developed in C++, whose source code is available at http://www.math.unipd.it/∼ranzato/SimEquiv/SimEquiv.zip together with the benchmark suite. We also implemented the HHK algorithm in C++ in order to experimentally compare the time and space perfor-mances of SimEquiv3 and HHK. In order to make the comparison as meaningful as possible, these two C++ implementations use the same data structures for representing transitions systems, sets of states and partitions.
Our benchmarks include systems from the well-known VLTS (Very Large Transition Systems) [30]
benchmark suite and some publicly available Esterel programs. These systems are represented as labelled transition systems where labels are attached to transitions. Since SimEquiv3 and HHK both need as input a Kripke structure, namely a transition system where labels are attached to states, we exploited a procedure designed by Dovier et al. [15] that transforms an edge-labeled graph G into a node-labeled graph G" in a way such that bisimulation equivalences on G and G" coincide. This conversion acts as follows: any transition s1 l
−
→ s2is replaced by two transitions s1→ n and n → s2, where n is a new node
1 Initialize(PartitionRelation P) {
2 for all B in P do {
3 B.Remove = Σ ! pre!(∪{C in P | Rel(B,C)});
4 for all x in Σ {B.BlockCount(x)=0; B.RelCount(x)=0;}
5 }
6 for all B in P do
7 for all y in B do
8 for all x in pre!({y}) do B.BlockCount(x)++;
9 for all B in P do
10 for all C in P such that Rel(B,C) do B.RelCount(x) += C.BlockCount(x);
11 }
20 ListOfBlocks RemoveList = {D ∈ P | D ⊆ Remove};
21 for all C in P such that (C ∩ pre!(Bprev) ,= ∅) do
Figure 7: C++ Pseudocode Implementation of the Efficient Simulation Equivalence Algorithm.
that is labeled with l. Hence, this transformation grows the size of the graph as follows: the number of transitions is doubled and the number of nodes of G"is the sum of the number of nodes and edges of G. The vasy * and cwi * systems are taken from the VLTS suite, while the remaining systems are the following Esterel programs: WristWatch and ShockDance are taken from the programming examples of Esterel [16], ObsArbitrer4 and AtLeastOneAck4 are described in the technical report [2], lift, NoAckWithoutReq and one pump are provided together with the fc2symbmin tool that is used by Xeve, a graphical verification environment for Esterel programs [3, 31].
Our experimental evaluation was carried out on an Intel Core 2 Duo 1.86 GHz PC, with 2 GB RAM, running Linux 2.6.20 and GNU g++ 4.1.2. The results are summarised in Table 1, where we list the name of the original transition system, the number of states and transitions of the transformed transition system, the number of blocks of the initial partition, the number of blocks of the final simulation equivalence partition (that is known when one algorithm terminates), the execution time in seconds and the allocated memory in MB of HHK and SimEquiv3, where o.o.m. means that the algorithm run out of memory (2GB).
The experiments show that SimEquiv3improves on HHK of two orders of magnitude in time and of one order of magnitude in space. In fact, the sum of time and space measures on the eight systems where both HHK and SimEquiv3terminate is 142.17 vs. 2.06 seconds in time and 1512.568 vs. 206.492 MB in space. Also, the size of systems (states plus edges) where SimEquiv3terminates w.r.t. HHK grows about one order of magnitude.
9 Conclusion
We presented a new efficient algorithm for computing simulation equivalence in O(|Psim||!|)-time and O(|Psim||Σ|)-space, where Psimis the partition induced by simulation equivalence on some Kripke struc-ture (Σ, !). This improves the best available time bound O(|Σ||!|) given by Henzinger, Henzinger and Kopke’s [21] and by Bloom and Paige’s [1] algorithms that however suffer from a quadratic space
complex-HHK SimEquiv3
Model States Trans. Init. B. SimEq B. Time Space Time Space
cwi 1 2 4339 4774 27 2959 15.77 508 1.10 104
cwi 3 14 18548 29104 3 123 – o.o.m. 0.13 15
vasy 0 1 1513 2448 3 43 0.69 56 0.01 0.797
vasy 10 56 67005 112312 13 ?? – o.o.m. – o.o.m.
vasy 1 4 5647 8928 7 2805 24.99 844 0.76 82
vasy 18 73 91789 146086 18 ?? – o.o.m. – o.o.m.
vasy 25 25 50433 50432 25217 ?? – o.o.m. – o.o.m.
vasy 40 60 100013 120014 4 ?? – o.o.m. – o.o.m.
vasy 5 9 15162 19352 32 13173 – o.o.m. 17.52 906
vasy 8 24 33290 48822 12 ?? – o.o.m. – o.o.m.
vasy 8 38 47345 76848 82 ?? – o.o.m. – o.o.m.
WristWatch 1453 1685 23 891 0.70 57 0.100 10
ShockDance 379 459 10 291 0.47 3 0.01 1
ObsArbitrer4 17389 21394 10 8311 – o.o.m. 6.80 623
AtLeastOneAck4 435 507 18 159 0.56 5 0.01 0.955
lift 138 163 33 118 0.50 0.568 0.00 0.740
NoAckWithoutReq 1212 1372 18 452 0.48 39 0.07 7
one pump 15774 17926 22 7606 – o.o.m. 7.13 650
Table 1: Results of the experimental evaluation.
ity that is bounded from below by Ω(|Σ|2). A better space bound is given by Gentilini et al.’s [17] algorithm whose space complexity is in O(|Psim|2+ |Σ| log(|Psim|)), but that runs in O(|Psim|2|!|)-time. Our al-gorithm is designed as an adaptation of Henzinger et al.’s procedure and abstract interpretation techniques are used for proving its correctness.
As future work, we plan to investigate whether the techniques used for designing this new simulation equivalence may be generalized and adapted for other behavioural equivalences like branching bisimulation [14]. It is also definitely interesting whether this new algorithm may admit a symbolic version based on BDDs.
Acknowledgements. This work was partially supported by the FIRB Project “Abstract interpretation and model checking for the verification of embedded systems”, by the PRIN Project “AIDA: Abstract Inter-pretation Design and Applications” and by the University of Padova under the Project “Formal methods for specifying and verifying behavioural properties of software systems”. This paper is an extended and revised version of [28].
References
[1] B. Bloom and R. Paige. Transformational design and implementation of a new efficient solution to the ready simulation problem. Sci. Comp. Program., 24(3):189-220, 1995.
[2] A. Bouali. Xeve: an Esterel Verification Environment (version v1 3). Rapport Technique 214/1997, INRIA, 1997.
[3] A. Bouali. Xeve: an Esterel verification environment. In Proc. 10th CAV, LNCS 1427, pp. 500-504, 1998.
[4] M.C. Browne, E.M. Clarke and O. Grumberg. Characterizing finite Kripke structures in propositional temporal logic. Theor. Comp. Sci., 59:115-131, 1988.
[5] D. Bustan and O. Grumberg. Simulation-based minimization. ACM Trans. Comput. Log., 4(2):181-204, 2003.
[6] U. Celikkan and R. Cleaveland. Generating diagnostic information for behavioral preorders. Dis-tributed Computing, 9:61-75, 1995.
[7] E.M. Clarke, O. Grumberg, S. Jha, Y. Lu, H. Veith. Progress on the state explosion problem in model checking. In Informatics - 10 Years Back, 10 Years Ahead. LNCS 2000, pp. 176-194, 2001.
[8] E.M. Clarke, O. Grumberg and D. Long. Model checking and abstraction. ACM Trans. Program.
Lang. Syst., 16(5):1512–1542, 1994.
[9] E.M. Clarke, O. Grumberg and D.A. Peled. Model checking. The MIT Press, 1999.
[10] T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein. Introduction to Algorithms. The MIT Press and McGraw-Hill, 2nd ed., 2001.
[11] P. Cousot and R. Cousot. Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Proc. 4th ACM POPL, pp. 238–252, 1977.
[12] P. Cousot and R. Cousot. Systematic design of program analysis frameworks. In Proc. 6th ACM POPL, pp. 269–282, 1979.
[13] D. Dams, O. Grumberg and R. Gerth. Generation of reduced models for checking fragments of CTL.
In Proc. 5th CAV, LNCS 697, pp. 479–490, 1993.
[14] R. De Nicola and F. Vaandrager. Three logics for branching bisimulation. J. ACM, 42(2):458–487, 1995
[15] A. Dovier, C. Piazza and A. Policriti. An efficient algorithm for computing bisimulation equivalence.
Theor. Comput. Sci., 325(1):45-67, 2004.
[16] Esterel Programming Examples. http://www-sop.inria.fr/esterel.org/Html/Downloads/Downloads.htm [17] R. Gentilini, C. Piazza and A. Policriti. From bisimulation to simulation: coarsest partition problems.
J. Automated Reasoning, 31(1):73-103, 2003.
[18] R. Giacobazzi and E. Quintarelli. Incompleteness, counterexamples and refinements in abstract model checking. In Proc. 8th SAS, LNCS 2126, pp. 356-373, 2001.
[19] R. Giacobazzi and F. Ranzato. Optimal domains for disjunctive abstract interpretation. Sci. Comp.
Program., 32:177–210, 1998.
[20] O. Grumberg and D.E. Long. Model checking and modular verification. ACM Trans. Program. Lang.
Syst., 16(3):843–871, 1994.
[21] M.R. Henzinger, T.A. Henzinger and P.W. Kopke. Computing simulations on finite and infinite graphs. In Proc. 36th FOCS, pp. 453–462, 1995.
[22] P.C. Kanellakis and S.A. Smolka. CCS expressions, finite state processes, and three problems of equivalence. Information and Computation, 86(1):43-68, 1990.
[23] A. Kucera and R. Mayr. Simulation preorder over simple process algebras. Information and Compu-tation, 173(2):184-198, 2002.
[24] A. Kucera and R. Mayr. Why is simulation harder than bisimulation? In Proc. 13th CONCUR, LNCS 2421, pp. 594-610, 2002.
[25] C. Loiseaux, S. Graf, J. Sifakis, A. Bouajjani and S. Bensalem. Property preserving abstractions for the verification of concurrent systems. Formal Methods in System Design, 6:1–36, 1995.
[26] R. Paige and R.E. Tarjan. Three partition refinement algorithms. SIAM J. Comput., 16(6):973-989, 1987
[27] F. Ranzato and F. Tapparo. Generalized strong preservation by abstract interpretation. J. Logic and Computation, 17(1):157-197, 2007.
[28] F. Ranzato and F. Tapparo. A new efficient simulation equivalence algorithm. In Proc. 22nd IEEE Symp. on Logic in Computer Science (LICS’07), pp. 171–180, IEEE Press, 2007.
[29] L. Tan and R. Cleaveland. Simulation revisited. In Proc. 7thTACAS, LNCS 2031, pp. 480–495, 2001.
[30] The VLTS Benchmark Suite. http://www.inrialpes.fr/vasy/cadp/resources/benchmark bcg.html [31] Xeve: Esterel Verification Environment. http://www-sop.inria.fr/meije/verification/Xeve