Ontologically correct taxonomies by construction

Taxonomies play a central role in conceptual domain modeling, having a direct impact in areas such as knowledge representation, ontology engineering, and software engineering, as well as knowledge organization in information sciences. Despite this, there is little guidance on how to build high-quality taxonomies, with notable exceptions being the OntoClean methodology, and the ontology-driven conceptual modeling language OntoUML. These techniques take into account the ontological meta-properties of types to establish well-founded rules on the formation of taxonomic structures. In this paper, we show how to leverage the formal rules underlying these techniques in order to build taxonomies which are correct by construction. We define a set of correctness-preserving operations to systematically introduce types and subtyping relations into taxonomic structures. In addition to considering the ontological micro-theory of endurant types underlying OntoClean and OntoUML, we also employ the MLT (Multi-Level Theory) micro-theory of high-order types, which allows us to address multi-level taxonomies based on the powertype pattern. To validate our proposal, we formalize the model building operations as a graph grammar that incorporates both micro-theories. We apply automatic verification techniques over the grammar language to show that the graph grammar is sound, i.e., that all taxonomies produced by the grammar rules are correct, at least up to a certain size. We also show that the rules can generate all correct taxonomies up to a certain size (a completeness result).