Loading...
Please wait, while we are loading the content...
Similar Documents
Complexity boundaries for full satisfiability of restricted UML class diagrams
| Content Provider | Semantic Scholar |
|---|---|
| Author | Garćıa, Yazmı́n Angélica Ibáñez |
| Copyright Year | 2009 |
| Abstract | During the last years, the Unified Modeling Language (UML) has emerged as the de-facto standard language in the object-oriented analysis and design world. UML Class diagrams are one of the most important components of UML. Class diagrams provide a static description of system components. These diagrams describe systems structure in terms of classes, associations (relations between classes), and constraints imposed on classes and their inter-relationships. It has long been argued that due to their lack of semantics, the effective use of graphical notations can be problematic when applied to the development of non-trivial systems. However, the semantics of UML class diagrams is by now well established, and one can exploit automated reasoning tools that are based on the languages underlying their formalization to detect relevant properties, such as class satisfiability and subsumption. A fundamental reasoning task is detecting full satisfiability of a diagram, i.e., whether all classes and associations of the diagram can be simultaneously populated without violating any constraints of the diagram. The importance of detecting full satisfiability of a UML class diagram is supported by the fact that unsatisfiable classes or associations indicate that the diagram contains unnecessary information, or that there is a modeling error, such as over constraining. One key element in the development of methods for implementing these reasoning tasks, is the study of the intrinsic complexity of such tasks. While the complexity of class satisfiability has been studied extensively, full satisfiability received less attention. In this thesis, we address the complexity of full satisfiability of UML class diagrams. Specifically, we establish tight upper and lower bounds for full satisfiability of UML class diagrams under different combinations of constraints. The results presented here confirm the intuition that full satisfiability has the same computational complexity as class satisfiability. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.emcl-study.eu/fileadmin/master_theses/thesis_ibanez.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
