{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,6]],"date-time":"2026-01-06T04:53:31Z","timestamp":1767675211382,"version":"3.41.0"},"publisher-location":"New York, New York, USA","reference-count":21,"publisher":"ACM Press","license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Collaborative Research Center SFB HAEC","award":["912"],"award-info":[{"award-number":["912"]}]},{"name":"Research Training Group QuantLA - German Research Foundation (DFG)","award":["1763"],"award-info":[{"award-number":["1763"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1145\/3184558.3191618","type":"proceedings-article","created":{"date-parts":[[2018,4,18]],"date-time":"2018-04-18T18:04:25Z","timestamp":1524074665000},"page":"1603-1607","source":"Crossref","is-referenced-by-count":4,"title":["The Data Complexity of Answering Instance Queries in<i>FL0<\/i>"],"prefix":"10.1145","author":[{"given":"Franz","family":"Baader","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t Dresden, Dresden, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pavlos","family":"Marantidis","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Dresden, Dresden, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maximilian","family":"Pensel","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Dresden, Dresden, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","reference":[{"key":"key-10.1145\/3184558.3191618-1","unstructured":"Franz Baader. 1990. Terminological Cycles in KL-ONE-based Knowledge Representation Languages Proc. of the 8th Nat. Conf. on Artificial Intelligence (AAAI'90). Boston (Ma, USA), 621--626."},{"key":"key-10.1145\/3184558.3191618-2","unstructured":"Franz Baader, Sebastian Brandt, and Carsten Lutz. 2005. Pushing the $mathcalEL$ Envelope. In Proc. of the 19th Int. Joint Conf. on Artificial Intelligence (IJCAI 2005), Leslie Pack Kaelbling and Alessandro Saffiotti (Eds.). Morgan Kaufmann, Los Altos, Edinburgh (UK), 364--369."},{"key":"key-10.1145\/3184558.3191618-3","doi-asserted-by":"crossref","unstructured":"Franz Baader, Ian Horrocks, Carsten Lutz, and Ulrike Sattler. 2017. An Introduction to Description Logic. Cambridge University Press.","DOI":"10.1017\/9781139025355"},{"key":"key-10.1145\/3184558.3191618-4","doi-asserted-by":"crossref","unstructured":"Ronald J. Brachman, Deborah L. McGuinness, Peter F. Patel-Schneider, Lori Alperin Resnick, and Alexander Borgida. 1991. Living with CLASSIC: When and how to Use a KL-ONE-like Language. In Principles of Semantic Networks, John F. Sowa (Ed.). Morgan Kaufmann, Los Altos, 401--456.","DOI":"10.1016\/B978-1-4832-0771-1.50022-9"},{"key":"key-10.1145\/3184558.3191618-5","doi-asserted-by":"crossref","unstructured":"Ronald J. Brachman and James G. Schmolze. 1985. An Overview of the KL-ONE Knowledge Representation System. Cognitive Science Vol. 9, 2 (1985), 171--216.","DOI":"10.1207\/s15516709cog0902_1"},{"key":"key-10.1145\/3184558.3191618-6","unstructured":"Sebastian Brandt. 2004. Polynomial Time Reasoning in a Description Logic with Existential Restrictions, GCI Axioms, and--What Else. In Proc. of the 16th Eur. Conf. on Artificial Intelligence (ECAI 2004), Ramon L&#243;pez de M&#225;ntaras and Lorenza Saitta (Eds.). 298--302."},{"key":"key-10.1145\/3184558.3191618-7","doi-asserted-by":"crossref","unstructured":"Andrea Cal`&#305;, Georg Gottlob, and Thomas Lukasiewicz. 2012. A general Datalog-based framework for tractable query answering over ontologies. J. Web Sem. Vol. 14 (2012), 57--83.","DOI":"10.1016\/j.websem.2012.03.001"},{"key":"key-10.1145\/3184558.3191618-8","doi-asserted-by":"crossref","unstructured":"Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati. 2013. Data Complexity of Query Answering in Description Logics. Artificial Intelligence Vol. 195 (2013), 335--360.","DOI":"10.1016\/j.artint.2012.10.003"},{"key":"key-10.1145\/3184558.3191618-9","doi-asserted-by":"crossref","unstructured":"Ullrich Hustadt, Boris Motik, and Ulrike Sattler. 2007. Reasoning in Description Logics by a Reduction to Disjunctive Datalog. J. Autom. Reasoning Vol. 39, 3 (2007), 351--384.","DOI":"10.1007\/s10817-007-9080-3"},{"key":"key-10.1145\/3184558.3191618-10","unstructured":"Yevgeny Kazakov and Hans de Nivelle. 2003. Subsumption of concepts in $mathcalFL_0$ for (cyclic) terminologies with respect to descriptive semantics is PSPACE-complete Proc. of the 2003 Description Logic Workshop (DL 2003). CEUR Electronic Workshop Proceedings, http:\/\/CEUR-WS.org\/Vol-81\/."},{"key":"key-10.1145\/3184558.3191618-11","unstructured":"Alon Y. Levy and Marie-Christine Rousset. 1998. Verification of Knowledge Bases based on Containment Checking. Artificial Intelligence Vol. 101(1--2) (1998), 227--250."},{"key":"key-10.1145\/3184558.3191618-12","unstructured":"Carsten Lutz. 2008. The Complexity of Conjunctive Query Answering in Expressive Description Logics Proc. of the Int. Joint Conf. on Automated Reasoning (IJCAR 2008) (Lecture Notes in Artificial Intelligence), Alessandro Armando, Peter Baumgartner, and Gilles Dowek (Eds.). Springer-Verlag, 179--193."},{"key":"key-10.1145\/3184558.3191618-13","doi-asserted-by":"crossref","unstructured":"Carsten Lutz and Frank Wolter. 2017. The Data Complexity of Description Logic Ontologies. Logical Methods in Computer Science Vol. 13, 4 (2017).","DOI":"10.23638\/LMCS-13(4:7)2017"},{"key":"key-10.1145\/3184558.3191618-14","doi-asserted-by":"crossref","unstructured":"E. Mays, R. Dionne, and R. Weida. 1991. K-REP System Overview. SIGART Bull. Vol. 2, 3 (1991).","DOI":"10.1145\/122296.122310"},{"key":"key-10.1145\/3184558.3191618-15","doi-asserted-by":"crossref","unstructured":"Bernhard Nebel. 1990. Terminological Reasoning is Inherently Intractable. Artificial Intelligence Vol. 43 (1990), 235--249.","DOI":"10.1016\/0004-3702(90)90087-G"},{"key":"key-10.1145\/3184558.3191618-16","unstructured":"Magdalena Ortiz. 2013. Ontology Based Data Access: The Story So Far. In Proc. of the 7th Alberto Mendelzon Int. Workshop on Foundations of Data Management (CEUR Workshop Proceedings), Loreto Bravo and Maurizio Lenzerini (Eds.), Vol. Vol. 1087. http:\/\/ceur-ws.org\/Vol-1087\/keynote3.pdf"},{"key":"key-10.1145\/3184558.3191618-17","doi-asserted-by":"crossref","unstructured":"Christof Peltason. 1991. The BACK System--an Overview. SIGART Bull. Vol. 2, 3 (1991), 114--119.","DOI":"10.1145\/122296.122314"},{"key":"key-10.1145\/3184558.3191618-18","unstructured":"Maximilian Pensel. 2015. An automata based approach for subsumption w.r.t. general concept inclusions in the description logic FL_0. Master's thesis. Chair for Automata Theory, TU Dresden, Germany. See http:\/\/lat.inf.tu-dresden.de\/research\/mas."},{"key":"key-10.1145\/3184558.3191618-19","unstructured":"Riccardo Rosati. 2007. On Conjunctive Query Answering in EL Proc. of the 2007 Description Logic Workshop (DL 2007) (CEUR Workshop Proceedings), Diego Calvanese, Enrico Franconi, Volker Haarslev, Domenico Lembo, Boris Motik, Anni-Yasmin Turhan, and Sergio Tessaris (Eds.), Vol. Vol. 250. CEUR-WS.org."},{"key":"key-10.1145\/3184558.3191618-20","doi-asserted-by":"crossref","unstructured":"Andrea Schaerf. 1993. On the Complexity of the Instance Checking Problem in Concept Languages with Existential Quantification. J. of Intelligent Information Systems Vol. 2 (1993), 265--278.","DOI":"10.1007\/BF00962071"},{"key":"key-10.1145\/3184558.3191618-21","doi-asserted-by":"crossref","unstructured":"William A. Woods and James G. Schmolze. 1992. The KL-ONE Family. In Semantic Networks in Artificial Intelligence, F. W. Lehmann (Ed.). Pergamon Press, 133--178. Published as a special issue of Computers &#38; Mathematics with Applications, Volume 23, Number 2--9.","DOI":"10.1016\/0898-1221(92)90139-9"}],"event":{"number":"2018","sponsor":["IW3C2, International World Wide Web Conference Committee","SIGWEB, ACM Special Interest Group on Hypertext, Hypermedia, and Web"],"acronym":"WWW '18","name":"Companion of the The Web Conference 2018","start":{"date-parts":[[2018,4,23]]},"location":"Lyon, France","end":{"date-parts":[[2018,4,27]]}},"container-title":["Companion of the The Web Conference 2018 on The Web Conference 2018 - WWW '18"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3184558.3191618","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/dl.acm.org\/ft_gateway.cfm?id=3191618&ftid=1958468&dwn=1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T19:28:32Z","timestamp":1751570912000},"score":1,"resource":{"primary":{"URL":"http:\/\/dl.acm.org\/citation.cfm?doid=3184558.3191618"}},"subtitle":[],"proceedings-subject":"The Web Conference 2018","short-title":[],"issued":{"date-parts":[[2018]]},"references-count":21,"URL":"https:\/\/doi.org\/10.1145\/3184558.3191618","relation":{},"subject":[],"published":{"date-parts":[[2018]]}}}