Stronger reduction criteria for Local First Search

M.E. Kurban, Peter Niebert, Hongyang Qu, Walter Vogler

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    2 Citations (Scopus)


    Local First Search (LFS) is a partial order technique for reducing the number of states to be explored when trying to decide reachability of a local (component) property in a parallel system; it is based on an analysis of the structure of the partial orders of executions in such systems. Intuitively, LFS is based on a criterion that allows to guide the search for such local properties by limiting the “concurrent progress��? of components. In this paper, we elaborate the analysis of the partial orders in ques- tion and obtain related but significantly stronger criteria for reductions, show their relation to the previously established criterion, and discuss the algorithmics of the proposed improvement. Our contribution is both fundamental in providing better insights into LFS and practical in pro- viding an improvement of high potential.
    Original languageUndefined
    Title of host publicationProceedings of the Third International Colloquium on Theoretical Aspects of Computing
    EditorsKamel Barkaoui, Ana Cavalcanti, Antonio Cerone
    Place of PublicationBerlin
    Number of pages15
    ISBN (Print)978-3-540-48815-6
    Publication statusPublished - 26 Oct 2006

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer Verlag
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    • CR-D.1.3
    • EWI-6939
    • METIS-238679
    • IR-63438

    Cite this

    Kurban, M. E., Niebert, P., Qu, H., & Vogler, W. (2006). Stronger reduction criteria for Local First Search. In K. Barkaoui, A. Cavalcanti, & A. Cerone (Eds.), Proceedings of the Third International Colloquium on Theoretical Aspects of Computing (pp. 108-122). (Lecture Notes in Computer Science; Vol. 4281/2006). Berlin: Springer.