Title :
Saving Time in a Space-Efficient Simulation Algorithm
Author_Institution :
Eindhoven Univ. of Technol., Eindhoven, Netherlands
Abstract :
We present an efficient algorithm for computing the simulation preorder and equivalence for labeled transition systems. The algorithm improves an existing space-efficient algorithm and improves its time complexity by employing a variant of the stability condition and exploiting properties of the underlying relations and partitions. It has comparable space and time complexity with the most efficient counterpart algorithms for Kripke structures.
Keywords :
computational complexity; formal verification; Kripke structure; equivalence; labeled transition system; saving time; simulation preorder; space-efficient simulation algorithm; stability condition; time complexity; Complexity theory; Computational modeling; Minimization; Partitioning algorithms; Software algorithms; Sorting; Stability analysis; Minimization methods; discrete-event systems; formal languages;
Conference_Titel :
Quality Software (QSIC), 2011 11th International Conference on
Conference_Location :
Madrid
Print_ISBN :
978-1-4577-0754-4
Electronic_ISBN :
1550-6002
DOI :
10.1109/QSIC.2011.26
