On the Hardness of Generating Cyclic Profiles of Robustness Diagram with Loop and Time Controls
摘要
Cyclic profiles of Robustness Diagram with Loop and Time Controls (or RDLT) are important for verifying its various model properties such as free-choiceness, well-handledness, diametrically-synched, etc. However, there is a lack of algebraic representations and relevant algorithms formulated in aid of efficient automation of generating these cyclic profiles in RDLTs. In the context of this research, such cyclic profiles create partitions of an RDLT, relative to each of its vertices, that influence its reachability, reusability, and synchronization considerations relative to the other vertices of the model. By way of problem reduction, this study proved that generating these RDLT cyclic profiles is equivalent to the problem of generating all the DFS trees of a digraph corresponding to the input RDLT and identifying its set of back edges. Furthermore, this paper provides a matrix-based framework in generating these cyclic profiles and reports its space and time complexity.