Stronger reduction criteria for Local First Search

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

doi:10.1007/11921240_8

Stronger reduction criteria for Local First Search

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

3 Citations (Scopus)

2 Downloads (Pure)

Abstract

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 language	Undefined
Title of host publication	Proceedings of the Third International Colloquium on Theoretical Aspects of Computing
Editors	Kamel Barkaoui, Ana Cavalcanti, Antonio Cerone
Place of Publication	Berlin
Publisher	Springer
Pages	108-122
Number of pages	15
ISBN (Print)	978-3-540-48815-6
DOIs	https://doi.org/10.1007/11921240_8
Publication status	Published - 26 Oct 2006
Event	Third International Colloquium on Theoretical Aspects of Computing, Tunis, Tunisia: Proceedings of the Third International Colloquium on Theoretical Aspects of Computing - Berlin Duration: 26 Oct 2006 → …

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Verlag
Volume	4281/2006
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	Third International Colloquium on Theoretical Aspects of Computing, Tunis, Tunisia
City	Berlin
Period	26/10/06 → …

Keywords

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

Access to Document

10.1007/11921240_8

http://eprints.eemcs.utwente.nl/secure2/6939/01/strongerlfs.pdf

Cite this

@inproceedings{63214814cd3b484daa79b3eb2e965f94,

title = "Stronger reduction criteria for Local First Search",

abstract = "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.",

keywords = "CR-D.1.3, EWI-6939, METIS-238679, IR-63438",

author = "M.E. Kurban and Peter Niebert and Hongyang Qu and Walter Vogler",

note = "10.1007/11921240_8 ; Third International Colloquium on Theoretical Aspects of Computing, Tunis, Tunisia ; Conference date: 26-10-2006",

year = "2006",

month = oct,

day = "26",

doi = "10.1007/11921240_8",

language = "Undefined",

isbn = "978-3-540-48815-6",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "108--122",

editor = "Kamel Barkaoui and Ana Cavalcanti and Antonio Cerone",

booktitle = "Proceedings of the Third International Colloquium on Theoretical Aspects of Computing",

}

Kurban, ME, 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. Lecture Notes in Computer Science, vol. 4281/2006, Springer, Berlin, pp. 108-122, Third International Colloquium on Theoretical Aspects of Computing, Tunis, Tunisia, Berlin, 26/10/06. https://doi.org/10.1007/11921240_8

Stronger reduction criteria for Local First Search. / Kurban, M.E.; Niebert, Peter; Qu, Hongyang et al.
Proceedings of the Third International Colloquium on Theoretical Aspects of Computing. ed. / Kamel Barkaoui; Ana Cavalcanti; Antonio Cerone. Berlin: Springer, 2006. p. 108-122 (Lecture Notes in Computer Science; Vol. 4281/2006).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Stronger reduction criteria for Local First Search

AU - Kurban, M.E.

AU - Niebert, Peter

AU - Qu, Hongyang

AU - Vogler, Walter

N1 - 10.1007/11921240_8

PY - 2006/10/26

Y1 - 2006/10/26

N2 - 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.

AB - 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.

KW - CR-D.1.3

KW - EWI-6939

KW - METIS-238679

KW - IR-63438

U2 - 10.1007/11921240_8

DO - 10.1007/11921240_8

M3 - Conference contribution

SN - 978-3-540-48815-6

T3 - Lecture Notes in Computer Science

SP - 108

EP - 122

BT - Proceedings of the Third International Colloquium on Theoretical Aspects of Computing

A2 - Barkaoui, Kamel

A2 - Cavalcanti, Ana

A2 - Cerone, Antonio

PB - Springer

CY - Berlin

T2 - Third International Colloquium on Theoretical Aspects of Computing, Tunis, Tunisia

Y2 - 26 October 2006

ER -