Algorithm to reduce the combinatorial complexity of a process graph

• Main Author: Marcos, Nelson
• Format: text
• Language: English
• Published: Animo Repository 1994
• Subjects: Algorithms; Combinatorial analysis; Graph theory > Data processing; Computational complexity; Electronic data processing; Machine theory; Computer Sciences
• Online Access: https://animorepository.dlsu.edu.ph/etd_masteral/1609; https://animorepository.dlsu.edu.ph/cgi/viewcontent.cgi?article=8447&context=etd_masteral
• Institution: De La Salle University

Given n processes submitted to a system for execution, there are n! possible ways to schedule the n processes. However, some of these schedules are not feasible due to time constraints. To lessen the number of candidate schedules, the infeasible schedules must be removed. By using defined process algebra axioms and theorems, the problem of reducing the combinatorial complexity of a process graph corresponding to a process expression that represents the possible schedules for n processes is resolved. Existing and new sets of notations and nomenclatures are used to describe processes and their time properties. These time properties are incorporated into the process graph representing a process expression. This process graph is then reduced through an algorithm that applies newly defined reduction theorems.