Login | Register

Detection of separable predicates on series-parallel systems


Detection of separable predicates on series-parallel systems

Dumais, Guy (1998) Detection of separable predicates on series-parallel systems. Masters thesis, Concordia University.

[thumbnail of MQ39483.pdf]
Text (application/pdf)


In this thesis, we address part of the predicate detection problem on distributed computations. We introduce two new classes of predicates, the monotonic predicates and the separable predicates. These classes generalize several classes of well-known predicates as the conjunctive predicates. We show that these classes are detected efficiently on distributed computations having the series-parallel property. This deviates from the approach used in the past where the detection problem was addressed for small classes of predicates to be detected on general distributed computations. The detection algorithm is based on a decomposition of the state lattice into simple subsets called concurrent intervals. This decomposition has its own interest since it helps understanding the relation between the complexity of the state lattice and the complexity of the event structure. At the heart of this relation is a new structure: the communication graph. We show that the communication graph gives a suitable level of abstraction to deal with the predicate detection problem.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Dumais, Guy
Pagination:x, 88 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Dept. of Computer science
Thesis Supervisor(s):Li, H. F
Identification Number:QA 76.9 D5D86 1998
ID Code:623
Deposited By: Concordia University Library
Deposited On:27 Aug 2009 17:13
Last Modified:13 Jul 2020 19:47
Related URLs:
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top