Reasoning on UML Class Diagrams is ExpTime-hard

Proc. of the 16th Int. Workshop on Description Logics (DL 2003). Volume 81 of CEUR Workshop Proceedings, https://ceur-ws.org/. 2003.

UML is the de-facto standard formalism for software design and analysis. One of the most important components of UML are class diagrams, which model the information on the domain of interest in terms of objects organized in classes and relationships between them. To support the design of large-scale industrial applications, CASE tools should be equipped with automated reasoning capabilities in order to detect relevant formal properties of UML diagrams, such as inconsistencies or redundancies. However, reasoning on UML class diagrams is fairly complex: in this paper we show that it is EXPTIME-hard.

@inproceedings{DL-2003-uml,
   title = "Reasoning on UML Class Diagrams is ExpTime-hard",
   year = "2003",
  author = "Daniela Berardi and Diego Calvanese and De Giacomo, Giuseppe",
   booktitle = "Proc. of the 16th Int. Workshop on Description Logics
(DL 2003)",
   pages = "28--37",
   volume = "81",
   publisher = "CEUR-WS.org",
   series = "CEUR Workshop Proceedings, https://ceur-ws.org/",
}