{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T16:18:23Z","timestamp":1762100303890},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1993,9,1]],"date-time":"1993-09-01T00:00:00Z","timestamp":746841600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Intell Inf Syst"],"published-print":{"date-parts":[[1993,9]]},"DOI":"10.1007\/bf00962071","type":"journal-article","created":{"date-parts":[[2005,1,13]],"date-time":"2005-01-13T14:44:50Z","timestamp":1105627490000},"page":"265-278","source":"Crossref","is-referenced-by-count":41,"title":["On the complexity of the instance checking problem in concept languages with existential quantification"],"prefix":"10.1007","volume":"2","author":[{"given":"Andrea","family":"Schaerf","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"CR1","volume-title":"Proc. Workshop on Processing Declarative Knowledge, PDK-19.","author":"F. Baader","year":"1991","unstructured":"Baader, F. & Hollunder, B. (1991). A Terminological Knowledge Representation System with Complete Inference Algorithm. InProc. Workshop on Processing Declarative Knowledge, PDK-19. Lecture Notes in Artificial Intelligence. Springer-Verlag: New York."},{"key":"CR2","unstructured":"Brachman, R.J. & Levesque, H.J. (1984). The Tractability of Subsumption in Frame-Based Description Languages. InProc. 4th Nat. Conf. on Artificial Intelligence AAAI-84."},{"key":"CR3","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0004-3702(92)90076-A","volume":"2?3","author":"F.M. Donini","year":"1992","unstructured":"Donini, F.M., Hollunder, B., Lenzerini, M., Marchetti Spaccamela, A., Nardi, D. & Nutt, W.. (1992a). The Complexity of Existential Quantification in Concept Languages,Artificial Intelligence, 2?3, 309?327.","journal-title":"Artificial Intelligence"},{"key":"CR4","unstructured":"Donini, F.M., Lenzerini, M., Nardi, D. & Nutt, W. (1991). The Complexity of Concept Languages. In James Allen, Richard Fikes, and Erik Sandewall (Eds.),Proc. 2nd Int. Conf. on Principles of Knowledge Representation and Reasoning KR-91, pages 151?162, Morgan Kaufmann."},{"key":"CR5","unstructured":"Donini, F.M., Lenzerini, M., Nardi, D., Nutt, W. & Schaerf, A. (1992b). Adding Epistemic Operators to Concept Languages. InProc. 3rd Int. Conf. On Principles of Knowledge Representation and Reasoning KR-92, pages 342?353."},{"key":"CR6","unstructured":"Donini, F.M., Lenzerini, M., Nardi, D. & Schaerf, A. (1992c). From Subsumption to Instance Checking, Technical Report 15.92, Dipartimento di Informatica e Sistemistica, Universita di Roma ?La Sapienza.?"},{"key":"CR7","volume-title":"Computers and Intractability?A guide to NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R. & Johnson, D.S. (1979).Computers and Intractability?A guide to NP-completeness, Freeman: San Francisco."},{"key":"CR8","unstructured":"Lenzerini, M. & Schaerf, A. (1991a). Concept Languages as Query Languages. InProc. 9th Nat. Conf. on Artificial Intelligence AAAI-91."},{"key":"CR9","volume-title":"Proc. Workshop on Processing Declarative Knowledge, PDK-91","author":"M. Lenzerini","year":"1991","unstructured":"Lenzerini, M. & Schaerf, A. (1991b). Querying Concept-Based Knowledge Bases. InProc. Workshop on Processing Declarative Knowledge, PDK-91, Lecture Notes in Artificial Intelligence. Springer-Verlag: New York."},{"key":"CR10","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1111\/j.1467-8640.1987.tb00176.x","volume":"3","author":"H.J. Levesque","year":"1987","unstructured":"Levesque, H.J. & Brachman, R.J. (1987). Expressiveness and Tractability in Knowledge Representation and Reasoning,Computational Intelligence, 3, 78?93.","journal-title":"Computational Intelligence"},{"issue":"3","key":"CR11","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1145\/122296.122309","volume":"2","author":"R. MacGregor","year":"1991","unstructured":"MacGregor, R. (1991). Inside the LOOM Description Classifier,SIGART Bulletin, 2(3); 88?92.","journal-title":"SIGART Bulletin"},{"issue":"3","key":"CR12","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1016\/0004-3702(88)90066-5","volume":"34","author":"B. Nebel","year":"1988","unstructured":"Nebel, B. (1988). Computational Complexity of Terminological Reasoning in BAck,Artificial Intelligence, 34(3), 371?383.","journal-title":"Artificial Intelligence"},{"key":"CR13","volume-title":"Lecture Notes in Artificial Intelligence","author":"B. Nebel","year":"1990","unstructured":"Nebel, B. (1990a)Reasoning and Revision in Hybrid Representation Systems, Lecture Notes in Artificial Intelligence. Springer-Verlag: New York."},{"key":"CR14","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0004-3702(90)90087-G","volume":"43","author":"B. Nebel","year":"1990","unstructured":"Nebel, B. (1990b). Terminological Reasoning is Inherently Intractable.Artificial Intelligence, 43, 235?249.","journal-title":"Artificial Intelligence"},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"Nebel, B. (1991). Terminological Cycles: Semantics and Computational Properties. In John F. Sowa (ed.),Principles of Semantic Networks, pages 331?361. Morgan Kaufmann.","DOI":"10.1016\/B978-1-4832-0771-1.50018-7"},{"issue":"3","key":"CR16","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1145\/122296.122313","volume":"2","author":"P.F. Patel-Schneider","year":"1991","unstructured":"Patel-Schneider, P.F., McGuiness, D.L., Brachman, R.J., Alperin Resnick, L. & Borgida, A. (1991). The Classic Knowledge Representation System: Guiding Principles and Implementation Rationale.SIGART Bulletin, 2(3); 108?113.","journal-title":"SIGART Bulletin"},{"issue":"3","key":"CR17","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/122296.122314","volume":"2","author":"C. Peltason","year":"1991","unstructured":"Peltason, C. (1991). The BACK System-An Overview,SIGART Bulletin, 2(3); 114?119.","journal-title":"SIGART Bulletin"},{"key":"CR18","unstructured":"Schmidt-Schau?, M. (1989). Subsumption in KL-ONE Is Undecidable. In Ron J. Brachman, Hector J. Levesque, and Ray Reiter Ed,Proc. 1st Int. Conf. on Principles of Knowledge Representation and Reasoning KR-89. Morgan Kaufmann."},{"issue":"1","key":"CR19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0004-3702(91)90078-X","volume":"48","author":"M. Schmidt-Schau?","year":"1991","unstructured":"Schmidt-Schau?, M. & Smolka, G. (1991). Attributive Concept Descriptions with Complements,Artificial Intelligence, 48(1), 1?26.","journal-title":"Artificial Intelligence"},{"key":"CR20","unstructured":"Vardi, M. (1982). The Complexity of Relational Query Languages.In14th ACM Symp. on Theory of Computing, pages 137?146."}],"container-title":["Journal of Intelligent Information Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00962071.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF00962071\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00962071","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,29]],"date-time":"2019-04-29T18:29:16Z","timestamp":1556562556000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF00962071"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,9]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1993,9]]}},"alternative-id":["BF00962071"],"URL":"https:\/\/doi.org\/10.1007\/bf00962071","relation":{},"ISSN":["0925-9902","1573-7675"],"issn-type":[{"value":"0925-9902","type":"print"},{"value":"1573-7675","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,9]]}}}