Saving time in a space-efficient simulation algorithm

J. Markovski

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-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 languageEnglish
    Title of host publicationProceedings of the 11th International Conference on Quality Software (QSIC 2011), 13-14 July 2011, Madrid, Spain
    PublisherInstitute of Electrical and Electronics Engineers
    Pages244-251
    DOIs
    Publication statusPublished - 2011

    Cite this