Saving time in a space-efficient simulation algorithm

J. Markovski

    Research output: Book/ReportReportAcademic

    178 Downloads (Pure)


    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
    Place of PublicationEindhoven
    PublisherTechnische Universiteit Eindhoven
    Number of pages19
    Publication statusPublished - 2011

    Publication series

    NameSE report
    ISSN (Print)1872-1567


    Dive into the research topics of 'Saving time in a space-efficient simulation algorithm'. Together they form a unique fingerprint.

    Cite this