DocumentCode
3073985
Title
Saving Time in a Space-Efficient Simulation Algorithm
Author
Markovski, J.
Author_Institution
Eindhoven Univ. of Technol., Eindhoven, Netherlands
fYear
2011
fDate
13-14 July 2011
Firstpage
244
Lastpage
251
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Quality Software (QSIC), 2011 11th International Conference on
Conference_Location
Madrid
ISSN
1550-6002
Print_ISBN
978-1-4577-0754-4
Electronic_ISBN
1550-6002
Type
conf
DOI
10.1109/QSIC.2011.26
Filename
6004333
Link To Document