{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,7]],"date-time":"2026-08-07T17:13:04Z","timestamp":1786122784378,"version":"build-2736575974"},"reference-count":46,"publisher":"SAGE Publications","issue":"2","license":[{"start":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:00:00Z","timestamp":1777593600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Applied Ontology"],"published-print":{"date-parts":[[2026,5]]},"abstract":"<jats:p>\n                    The field of computational complexity theory is a core theoretical subject in computer science with significant impact also for real-world applications. Although a plethora of individual results are known, a systematic conceptual organisation of this knowledge is still lacking. We propose a modelling approach for creating an ontologically well-founded knowledge base for the theory of computational complexity that will enable storing, querying and reasoning over the vast knowledge of algorithmic problems, complexity classes and their relationships. We determine the core concepts and relations of complexity theory and model them on two levels of approximation: a lightweight version based on the decidable description logic\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" overflow=\"scroll\">\n                        <mml:mrow>\n                          <mml:mrow>\n                            <mml:mi mathvariant=\"script\">S<\/mml:mi>\n                            <mml:mi mathvariant=\"script\">R<\/mml:mi>\n                            <mml:mi mathvariant=\"script\">O<\/mml:mi>\n                            <mml:mi mathvariant=\"script\">I<\/mml:mi>\n                            <mml:mi mathvariant=\"script\">Q<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:mrow>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    (the underlying formalism of the ontology language OWL 2 DL) and a further extended version based on first-order logic.\n                  <\/jats:p>","DOI":"10.1177\/15705838261451614","type":"journal-article","created":{"date-parts":[[2026,8,5]],"date-time":"2026-08-05T17:25:26Z","timestamp":1785950726000},"page":"99-121","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":0,"title":["Ontological Modelling Principles for Computational Complexity"],"prefix":"10.1177","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1499-2090","authenticated-orcid":false,"given":"Anton","family":"Gnatenko","sequence":"first","affiliation":[{"name":"Free University of Bozen-Bolzano"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1517-7354","authenticated-orcid":false,"given":"Oliver","family":"Kutz","sequence":"additional","affiliation":[{"name":"Free University of Bozen-Bolzano"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5763-6080","authenticated-orcid":false,"given":"Nicolas","family":"Troquard","sequence":"additional","affiliation":[{"name":"Gran Sasso Science Institute"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"179","published-online":{"date-parts":[[2026,8,5]]},"reference":[{"key":"e_1_3_4_2_1","doi-asserted-by":"crossref","unstructured":"Abiteboul S. Vianu V. (1989). Fixpoint extensions of first-order logic and datalog-like languages. In Proceedings of the Fourth Annual Symposium on Logic in Computer Science. https:\/\/doi.org\/10.1109\/LICS.1989.39160","DOI":"10.1109\/LICS.1989.39160"},{"key":"e_1_3_4_3_1","unstructured":"Amarilli A. Benedikt M. (2015). Combining existential rules and description logics. In Proceedings of the 24th International Conference on Artificial Intelligence. https:\/\/doi.org\/10.5555\/2832581.2832625"},{"key":"e_1_3_4_4_1","volume-title":"Computational complexity: A modern approach","author":"Arora S.","year":"2006","unstructured":"Arora S., Barak B. (2006). Computational complexity: A modern approach. Cambridge University Press. https:\/\/doi.org\/10.1017\/CBO9780511804090"},{"key":"e_1_3_4_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)91133-B"},{"key":"e_1_3_4_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204037"},{"key":"e_1_3_4_7_1","volume-title":"Handbook of satisfiability","author":"Biere A.","year":"2009","unstructured":"Biere A., Heule M., van Maaren H., Walsh T. (2009). Handbook of satisfiability. IOS Press. https:\/\/ebooks.iospress.nl\/volume\/handbook-of-satisfiability-second-edition"},{"key":"e_1_3_4_8_1","unstructured":"Bodily P. M. Ventura D. (2022). Open computational creativity problems in computational theory. In Proceedings of the 13th International Conference on Computational Creativity (ICCC). https:\/\/computationalcreativity.net\/iccc22\/papers\/ICCC-2022_paper_61.pdf."},{"key":"e_1_3_4_9_1","unstructured":"Brickley D. Guha R. (2004). RDF vocabulary description language 1.0: RDF Schema. https:\/\/w3.org\/2001\/sw\/RDFCore\/Schema\/200212bwm\/"},{"key":"e_1_3_4_10_1","doi-asserted-by":"crossref","unstructured":"Buneman P. Khanna S. Tan W. C. (2001). Why and where: A characterization of data provenance. In Proceedings of the 8th International Conference on Database Theory. https:\/\/doi.org\/10.1007\/3-540-44503-x_20","DOI":"10.1007\/3-540-44503-X_20"},{"key":"e_1_3_4_11_1","unstructured":"Calvanese D. Giacomo G. D. Lenzerini M. (1997). Conjunctive query containment in description logics with n-ary relations. In Proceedings of the 1997 International Workshop on Description Logics. https:\/\/dblp.org\/rec\/conf\/dlog\/CalvaneseGL97"},{"key":"e_1_3_4_12_1","unstructured":"Carlisle D. Writers P. Ausbrooks R. Buswell S. Dalmas S. Devitt S. Diaz A. Hunter R. Smith B. Soiffer N. Sutor R. Watt S. (2000). Mathematical markup language (MathML) version 2.0. World Wide Web. https:\/\/www.w3.org\/TR\/MathML2\/"},{"key":"e_1_3_4_13_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000006"},{"key":"e_1_3_4_14_1","doi-asserted-by":"publisher","DOI":"10.2307\/2269326"},{"key":"e_1_3_4_15_1","doi-asserted-by":"crossref","unstructured":"Cook S. A. (1971). The complexity of theorem-proving procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing (STOC). https:\/\/doi.org\/10.1145\/800157.805047","DOI":"10.1145\/800157.805047"},{"key":"e_1_3_4_16_1","first-page":"29","article-title":"OntoMathPRO: An ontology of mathematical knowledge","volume":"507","author":"Elizarov A. M.","year":"2022","unstructured":"Elizarov A. M., Kirillovich A. V., Lipachev E. K., Nevzorova O. A. (2022). OntoMathPRO: An ontology of mathematical knowledge. Doklady Mathematics. 507, 29. https:\/\/doi.org\/10.1134\/S1064562422700016","journal-title":"Doklady Mathematics"},{"key":"e_1_3_4_17_1","volume-title":"Science Without numbers: A defence of nominalism","author":"Field H.","year":"1980","unstructured":"Field H. (1980). Science Without numbers: A defence of nominalism. Oxford University Press. https:\/\/philpapers.org\/rec\/FIESWN-2"},{"issue":"2","key":"e_1_3_4_18_1","article-title":"When one logic is not enough: Integrating first-order annotations in OWL ontologies","volume":"16","author":"Fl\u00fcgel S.","year":"2024","unstructured":"Fl\u00fcgel S., Glauer M., Neuhaus F., Hastings J. (2024). When one logic is not enough: Integrating first-order annotations in OWL ontologies. Semantic Web Journal, 16(2).\u00a0https:\/\/doi.org\/10.3233\/SW-243440","journal-title":"Semantic Web Journal"},{"key":"e_1_3_4_19_1","unstructured":"Gnatenko A. Kutz O. Troquard N. (2024a). Building an ontology of computational complexity. In Proceedings of the Joint Ontology Workshops (JOWO). https:\/\/ceur-ws.org\/Vol-3882\/foust-9.pdf"},{"key":"e_1_3_4_20_1","doi-asserted-by":"crossref","unstructured":"Gnatenko A. Kutz O. Troquard N. (2024b). Modelling and mining knowledge about computational complexity. In Proceedings of the 24th International Conference on Knowledge Engineering and Knowledge Management (EKAW). https:\/\/doi.org\/10.1007\/978-3-031-77792-9_27","DOI":"10.1007\/978-3-031-77792-9_27"},{"key":"e_1_3_4_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2008.05.001"},{"key":"e_1_3_4_22_1","doi-asserted-by":"crossref","unstructured":"Green T. J. Karvounarakis G. Tannen V. (2007). Provenance semirings. In Proceedings of the 26th Symposium on Principles of Database Systems (PODS). https:\/\/doi.org\/10.1145\/1265530.1265535","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_3_4_23_1","unstructured":"Gr\u00fcninger M. Fox M. (1995). Methodology for the design and evaluation of ontologies. In Workshop on Basic Ontological Issues in Knowledge Sharing. https:\/\/eil.utoronto.ca\/wp-content\/uploads\/enterprise-modelling\/papers\/gruninger-ijcai95.pdf"},{"key":"e_1_3_4_24_1","doi-asserted-by":"publisher","DOI":"10.12775\/LLP.2016.007"},{"key":"e_1_3_4_25_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1965-0170805-7"},{"key":"e_1_3_4_26_1","unstructured":"Hern\u00e1ndez D. Hogan A. Kr\u00f6tzsch M. (2015). Reifying RDF: What works well with wikidata? In Proceedings of the 11th International Workshop on Scalable Semantic Web Knowledge Base Systems. https:\/\/ceur-ws.org\/Vol-1457\/SSWS2015_paper3.pdf"},{"key":"e_1_3_4_27_1","unstructured":"Horrocks I. Kutz O. Sattler U. (2006). The even more irresistible SROIQ. In Proceedings Tenth International Conference on Principles of Knowledge Representation and Reasoning Lake District of the United Kingdom June 2\u20135 2006. https:\/\/aaai.org\/Library\/KR\/2006\/kr06-009.php"},{"key":"e_1_3_4_28_1","doi-asserted-by":"crossref","unstructured":"Karp R. M. (1972). Reducibility among combinatorial problems. In Proceedings of the Symposium on the Complexity of Computer Computations. https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_3_4_29_1","doi-asserted-by":"crossref","unstructured":"Keet C. M. Kutz O. (2017). Orchestrating a network of mereo(topo)logical theories. In Proceedings of the 9th Knowledge Capture Conference. https:\/\/doi.org\/10.1145\/3148011.3148013","DOI":"10.1145\/3148011.3148013"},{"key":"e_1_3_4_30_1","volume-title":"Theory of computation (texts in computer science)","author":"Kozen D. C.","year":"2006","unstructured":"Kozen D. C. (2006). Theory of computation (texts in computer science). Springer-Verlag. https:\/\/dl.acm.org\/doi\/10.5555\/1137726"},{"key":"e_1_3_4_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/321864.321877"},{"key":"e_1_3_4_32_1","unstructured":"Landgrebe J. Smith B. (2023). Ontologies of common sense physics and mathematics. arXiv preprint. https:\/\/doi.org\/10.48550\/arXiv.2305.01560"},{"key":"e_1_3_4_33_1","doi-asserted-by":"publisher","DOI":"10.3233\/SW-2012-0059"},{"key":"e_1_3_4_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-07003-1"},{"key":"e_1_3_4_35_1","unstructured":"Mossakowski T. Kutz O. Codescu M. Lange C. (2013). The distributed ontology modeling and specification language. In Proceedings of the 7th International Workshop on Modular Ontologies. https:\/\/ceur-ws.org\/Vol-1081\/womo2013_invited_paper_1.pdf"},{"key":"e_1_3_4_36_1","doi-asserted-by":"crossref","unstructured":"Motik B. (2005). On the properties of metamodeling in OWL. In The Semantic Web \u2013 ISWC 2005. https:\/\/doi.org\/10.1007\/11574620_40","DOI":"10.1007\/11574620_40"},{"key":"e_1_3_4_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-10587-1_6"},{"key":"e_1_3_4_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0315-0860(75)90116-0"},{"issue":"2","key":"e_1_3_4_39_1","first-page":"91","article-title":"The design and implementation of VAMPIRE","volume":"15","author":"Riazanov A.","year":"2002","unstructured":"Riazanov A., Voronkov A. (2002). The design and implementation of VAMPIRE. AI Communications, 15(2,3), 91. https:\/\/doi.org\/10.5555\/1218615.1218620","journal-title":"AI Communications"},{"key":"e_1_3_4_40_1","doi-asserted-by":"crossref","unstructured":"Rudolph S. (2011). Foundations of description logics. In Reasoning Web: 7th International Summer School. https:\/\/doi.org\/10.1007\/978-3-642-23032-5_2","DOI":"10.1007\/978-3-642-23032-5_2"},{"key":"e_1_3_4_41_1","unstructured":"Sack H. (2005). NPBibSearch \u2013 An ontology augmented bibliographic search. In Proceedings of the 2nd Italian Semantic Web Workshop. https:\/\/ceur-ws.org\/Vol-166\/"},{"key":"e_1_3_4_42_1","unstructured":"Schena I. Asperti A. (2002). Towards a semantic web for formal mathematics [PhD Thesis] University of Bologna. Technical Report UBLCS-2002-6."},{"key":"e_1_3_4_43_1","unstructured":"Schenk S. Dividino R. Staab S. (2009). Reasoning with provenance trust and all that other meta knowlege in OWL. In Proceedings of the 1st International Conference on Semantic Web in Provenance Management (SWPM). https:\/\/ceur-ws.org\/Vol-526\/paper_3.pdf"},{"key":"e_1_3_4_44_1","volume-title":"Introduction to the theory of computation","author":"Sipser M.","year":"2013","unstructured":"Sipser M. (2013). Introduction to the theory of computation. Course Technology. https:\/\/doi.org\/10.1145\/230514.571645"},{"key":"e_1_3_4_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90061-X"},{"key":"e_1_3_4_46_1","unstructured":"Toman D. Weddell G. E. (2015). On the utility of CFDI. In Proceedings of the 28th International Workshop on Description Logics. https:\/\/ceur-ws.org\/Vol-1350\/paper-36.pdf"},{"key":"e_1_3_4_47_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s2-42.1.230"}],"container-title":["Applied Ontology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/15705838261451614","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/15705838261451614","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/15705838261451614","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,7]],"date-time":"2026-08-07T12:18:59Z","timestamp":1786105139000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/15705838261451614"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5]]},"references-count":46,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,5]]}},"alternative-id":["10.1177\/15705838261451614"],"URL":"https:\/\/doi.org\/10.1177\/15705838261451614","relation":{},"ISSN":["1570-5838","1875-8533"],"issn-type":[{"value":"1570-5838","type":"print"},{"value":"1875-8533","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5]]}}}