On the Computational Complezity of the Reachability Problem in UML Activity Diagrams

摘要：

The reachability problem, the problem of checking whether certain node can be reached from some initial settings such that all restrictions on flow of control are satisfied, arises frequently in various applications of Unified Modeling Language activity diagrams. However, the complexity of the problem, or in fact the complexity of any general problem in UML activity diagrams, has yet to be investigated. Towards this initiative, we specify a class of diagrams where the reachability problem is PSPACEcomplete. However, if one further condition is applied, it can be shown that the problem is NPcomplete.

作者: Xing Tan Michael Gruninger

作者单位: Semantic Technologies Laboratory Department of Mechanical and Industrial Engineering University of Toronto

会议类型: 国际会议

会议名称: 2009 IEEE International Conference on Intelligent Computing and Intelligent Systems(2009 IEEE 智能计算与智能系统国际会议)

会议地点: 上海

会议语种:英文

页码: 1475-1479

在线出版日期: 2009-11-20（万方平台首次上网日期，不代表论文的发表时间）