Saving time in a space-efficient simulation algorithm

J. Markovski

    Onderzoeksoutput: Boek/rapportRapportAcademic

    199 Downloads (Pure)

    Samenvatting

    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.
    Originele taal-2Engels
    Plaats van productieEindhoven
    UitgeverijTechnische Universiteit Eindhoven
    Aantal pagina's19
    StatusGepubliceerd - 2011

    Publicatie series

    NaamSE report
    Volume2011-03
    ISSN van geprinte versie1872-1567

    Vingerafdruk

    Duik in de onderzoeksthema's van 'Saving time in a space-efficient simulation algorithm'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit