Saving time in a space-efficient simulation algorithm

J. Markovski

doi:10.1109/QSIC.2011.26

Saving time in a space-efficient simulation algorithm

J. Markovski

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

5 Citations (Scopus)

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.

Original language	English
Title of host publication	Proceedings of the 11th International Conference on Quality Software (QSIC 2011), 13-14 July 2011, Madrid, Spain
Publisher	Institute of Electrical and Electronics Engineers
Pages	244-251
DOIs	https://doi.org/10.1109/QSIC.2011.26
Publication status	Published - 2011

Access to Document

10.1109/QSIC.2011.26

Cite this

@inproceedings{3973440284f84f369db8a01814107251,

title = "Saving time in a space-efficient simulation algorithm",

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.",

author = "J. Markovski",

year = "2011",

doi = "10.1109/QSIC.2011.26",

language = "English",

pages = "244--251",

booktitle = "Proceedings of the 11th International Conference on Quality Software (QSIC 2011), 13-14 July 2011, Madrid, Spain",

publisher = "Institute of Electrical and Electronics Engineers",

address = "United States",

}

Saving time in a space-efficient simulation algorithm. / Markovski, J.
Proceedings of the 11th International Conference on Quality Software (QSIC 2011), 13-14 July 2011, Madrid, Spain. Institute of Electrical and Electronics Engineers, 2011. p. 244-251.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Saving time in a space-efficient simulation algorithm

AU - Markovski, J.

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

U2 - 10.1109/QSIC.2011.26

DO - 10.1109/QSIC.2011.26

M3 - Conference contribution

SP - 244

EP - 251

BT - Proceedings of the 11th International Conference on Quality Software (QSIC 2011), 13-14 July 2011, Madrid, Spain

PB - Institute of Electrical and Electronics Engineers

ER -

Saving time in a space-efficient simulation algorithm

Abstract

Access to Document

Fingerprint

Cite this