Saving time in a space-efficient simulation algorithm

J. Markovski

    Research output: Book/ReportReportAcademic

    5 Citations (Scopus)
    99 Downloads (Pure)

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

    Publication series

    NameSE report
    Volume2011-03
    ISSN (Print)1872-1567

    Cite this