Abrams, Marc2013-06-192013-06-191993-09-01http://hdl.handle.net/10919/19775Certain parallel software performance evaluation problems are equivalent to computational geometric problems. Consider a timed transition system representing a parallel program: a set of variables, a set of states, an initial state, a transition function mapping a set to a set of successor states, and a description of the time between transitions. Given a timed transition system, the paper solves four problems: (1) state the necessary and sufficient conditions for a TES to contain a LCES; (2) given the initial starting time of each process, find a representation of the set of all possible TESs; (3) determine if any initial process starting times exist that lead to a LCES in which no process ever blocks; and (4) find the set of all possible LCESs.application/pdfenIn CopyrightTechnical reportTR-93-30http://eprints.cs.vt.edu/archive/00000372/01/TR-93-30.pdf