{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,18]],"date-time":"2025-05-18T06:10:04Z","timestamp":1747548604239,"version":"3.40.5"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[1997,3,1]],"date-time":"1997-03-01T00:00:00Z","timestamp":857174400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1997,3,1]],"date-time":"1997-03-01T00:00:00Z","timestamp":857174400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Annals of Mathematics and Artificial Intelligence"],"published-print":{"date-parts":[[1997,3]]},"DOI":"10.1023\/a:1018903705269","type":"journal-article","created":{"date-parts":[[2003,2,19]],"date-time":"2003-02-19T22:07:13Z","timestamp":1045692433000},"page":"147-168","source":"Crossref","is-referenced-by-count":3,"title":["``Possible is certain'' is desirable and can be expressive"],"prefix":"10.1007","volume":"19","author":[{"given":"Sergio","family":"Greco","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Domenico","family":"Sacc\u00e0","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"325415_CR1","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/0022-0000(91)90032-Z","volume":"43","author":"S. Abiteboul","year":"1991","unstructured":"S. Abiteboul and V. Vianu, DATALOG extensions for databases queries and updates, Journal of Computer and System Science 43 (1991) 62\u2013124.","journal-title":"Journal of Computer and System Science"},{"key":"325415_CR2","unstructured":"S. Abiteboul, R. Hull and V. Vianu, Foundations of Databases (Addison-Wesley, 1994)."},{"key":"325415_CR3","doi-asserted-by":"crossref","unstructured":"S. Abiteboul, E. Simon and V. Vianu, Non-deterministic languages to express deterministic transformations, in: Proc. ACM PODS Symp. (1990) pp. 218\u2013229.","DOI":"10.1145\/298514.298575"},{"key":"325415_CR4","doi-asserted-by":"crossref","unstructured":"C. Baral and V. Subrahmanian, Stable and extension class theory for logic programs and default logic, Journal of Automated Reasoning (1992) 345\u2013366.","DOI":"10.1007\/BF02341854"},{"issue":"1","key":"325415_CR5","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0022-0000(82)90012-5","volume":"25","author":"A. Chandra","year":"1982","unstructured":"A. Chandra and D. Harel, Structure and complexity of relational queries, Journal of Computer and System Sciences 25(1) (1982) 99\u2013128.","journal-title":"Journal of Computer and System Sciences"},{"key":"325415_CR6","unstructured":"P. Dung, Negation as hypotheses: an abductive foundation for logic programming, in: Proc. 8th Conf. on Logic Programming (1991) pp. 3\u201317."},{"key":"325415_CR7","doi-asserted-by":"crossref","unstructured":"T. Eiter, G. Gottlob and H. Mannila, Expressive power and complexity of disjunctive DATALOG, in: Proc. ACM PODS Symp., Minneapolis, USA (May 1994).","DOI":"10.1007\/3-540-57802-1_5"},{"key":"325415_CR8","doi-asserted-by":"crossref","unstructured":"T. Eiter, N. Leone and D. Sacc\u00e0, The expressive power of partial models for disjunctive deductive databases, in: Proc. Workshop on Logic in Databases (LID '96), San Miniato (July, 1996).","DOI":"10.1007\/BFb0031745"},{"key":"325415_CR9","unstructured":"R. Fagin, Generalized first-order spectra and polynomial-time recognizable sets, in: Complexity of Computation, ed. R. Karp, SIAM-AMS Proc., Vol. 7 (1974) pp. 43\u201373."},{"key":"325415_CR10","first-page":"1070","volume-title":"Proc. 5th Int. Conf. and Symp. on Logic Programming","author":"M. Gelfond","year":"1988","unstructured":"M. Gelfond and V. Lifschitz, The stable model semantics for logic programming, in: Proc. 5th Int. Conf. and Symp. on Logic Programming, MIT Press, Cambridge (1988) pp. 1070\u20131080."},{"key":"325415_CR11","unstructured":"F. Giannotti, S. Greco, D. Sacc\u00e0 and C. Zaniolo, Programming with non-determinism in deductive databases, Ann. of Math. and AI (this issue)."},{"key":"325415_CR12","doi-asserted-by":"crossref","unstructured":"F. Giannotti, D. Pedreschi, D. Sacc\u00e0 and C. Zaniolo, Non-determinism in deductive databases, in: Proc. 2nd Conf. on Deductive and Object-Oriented Databases (1991) pp. 129\u2013146.","DOI":"10.1007\/3-540-55015-1_7"},{"key":"325415_CR13","doi-asserted-by":"crossref","unstructured":"S. Greco, D. Sacc\u00e0 and C. Zaniolo, DATALOG queries with stratified negation and choice: from p to Dp, in: Proc. of the Fifth Int. Conf. on Database Theory (1995) pp. 82\u201396.","DOI":"10.1007\/3-540-58907-4_8"},{"key":"325415_CR14","unstructured":"S. Greco and D. Sacc\u00e0, A query language that captures the query hierarchy, unpublished manuscript (1995)."},{"key":"325415_CR15","doi-asserted-by":"crossref","unstructured":"S. Grumbach, Z. Lacroix and S. Lindell, Implicit definitions on finite structures, in: Proc. of the Conf. on Computer Science Logic (1995).","DOI":"10.1007\/3-540-61377-3_42"},{"key":"325415_CR16","unstructured":"Y. Gurevich, Logic and the challenge of computer science, in: Trends in Theoretical Computer Science, ed. E. Borger (Computer Science Press, 1988)."},{"issue":"4","key":"325415_CR17","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"N. Immerman, Languages which capture complexity classes, SIAM Journal on Computing 16(4) (1987) 760\u2013778.","journal-title":"SIAM Journal on Computing"},{"key":"325415_CR18","doi-asserted-by":"crossref","unstructured":"D.S. Johnson, A catalog of complexity classes, in: Handbook of Theoretical Computer Science, Vol. 1 (North-Holland, 1990).","DOI":"10.1016\/B978-0-444-88071-0.50007-2"},{"key":"325415_CR19","unstructured":"P.C. Kanellakis, Elements of relational database theory, in: Handbook of Theoretical Computer Science, Vol. 2 (North-Holland, 1991)."},{"key":"325415_CR20","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/0022-0000(91)90033-2","volume":"43","author":"P.G. Kolaitis","year":"1991","unstructured":"P.G. Kolaitis and C.H. Papadimitriou, Why not negation by fixpoint?, Journal of Computer and System Sciences 43 (1991) 125\u2013144.","journal-title":"Journal of Computer and System Sciences"},{"key":"325415_CR21","first-page":"416","volume-title":"Proc. 3rd Int. Conf. on Data and Knowledge Bases","author":"R. Krishnamurthy","year":"1988","unstructured":"R. Krishnamurthy and S.A. Naqvi, Non-deterministic choice in DATALOG, in: Proc. 3rd Int. Conf. on Data and Knowledge Bases (Morgan-Kaufmann, Los Altos, 1988) pp. 416\u2013424."},{"key":"325415_CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-83189-8","volume-title":"Foundations of Logic Programming","author":"J.W. Lloyd","year":"1987","unstructured":"J.W. Lloyd, Foundations of Logic Programming (Springer-Verlag, Berlin, 1987)."},{"issue":"3","key":"325415_CR23","doi-asserted-by":"crossref","first-page":"588","DOI":"10.1145\/116825.116836","volume":"38","author":"W. Marek","year":"1991","unstructured":"W. Marek and M. Truszcynski, Autoepistemic logic, J. of the ACM 38(3) (1991) 588\u2013619.","journal-title":"J. of the ACM"},{"key":"325415_CR24","unstructured":"C.H. Papadimitriou, Computational Complexity (Addison-Wesley, 1994)."},{"key":"325415_CR25","doi-asserted-by":"crossref","first-page":"445","DOI":"10.3233\/FI-1990-13404","volume":"13","author":"T.C. Przymusinski","year":"1990","unstructured":"T.C. Przymusinski, Well-founded semantics coincides with three-valued stable semantics, Foundamenta Informaticae 13 (1990) 445\u2013463.","journal-title":"Foundamenta Informaticae"},{"key":"325415_CR26","unstructured":"D. Sacc\u00e0, The expressive powers of stable models for bound and unbound DATALOG queries, Journal of Computer and System Science (to appear)."},{"issue":"5","key":"325415_CR27","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0020-0190(96)00067-1","volume":"58","author":"D. Sacc\u00e0","year":"1996","unstructured":"D. Sacc\u00e0, Multiple total stable models are definitely needed to solve unique solution programs, Information Processing Letters 58(5) (1996) 249\u2013254.","journal-title":"Information Processing Letters"},{"key":"325415_CR28","doi-asserted-by":"crossref","unstructured":"D. Sacc\u00e0 and C. Zaniolo, Stable models and non-determinism in logic programs with negation, in: Proc. ACM PODS Symp. (1990) pp. 205\u2013218.","DOI":"10.1145\/298514.298572"},{"key":"325415_CR29","unstructured":"D. Sacc\u00e0 and C. Zaniolo, Deterministic and non-deterministic stable models, submitted to Journal of Logic and Computation."},{"key":"325415_CR30","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1006\/jcss.1995.1053","volume":"51","author":"J.S. Schlipf","year":"1995","unstructured":"J.S. Schlipf, The expressive powers of the logic programming semantics, Journal of Computer and System Science 51 (1995) 64\u201386.","journal-title":"Journal of Computer and System Science"},{"key":"325415_CR31","unstructured":"J.D. Ullman, Principles of Database and Knowledge Base Systems, Vols. 1\u20132 (Computer Science Press, 1989)."},{"key":"325415_CR32","doi-asserted-by":"crossref","unstructured":"M.Y. Vardi, The complexity of relational query languages, in: Proc. ACM Symp. on Theory of Computing (1982) pp. 137\u2013146.","DOI":"10.1145\/800070.802186"},{"issue":"3","key":"325415_CR33","doi-asserted-by":"crossref","first-page":"620","DOI":"10.1145\/116825.116838","volume":"38","author":"A. Van Gelder","year":"1991","unstructured":"A. Van Gelder, K. Ross and J.S. Schlipf, The well-founded semantics for general logic programs, Journal of the ACM 38(3) (1991) 620\u2013650.","journal-title":"Journal of the ACM"},{"key":"325415_CR34","first-page":"125","volume":"43","author":"A. Van Gelder","year":"1992","unstructured":"A. Van Gelder, The alternating fixpoint of logic programming with negation, Journal of Computer and System Sciences 43 (1992) 125\u2013144.","journal-title":"Journal of Computer and System Sciences"},{"key":"325415_CR35","doi-asserted-by":"crossref","unstructured":"J. You and L.Y. Yuan, On the equivalence of semantics for normal logic programs, Journal of Logic Programming (1995) 211\u2013222.","DOI":"10.1016\/0743-1066(94)00023-Y"}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1018903705269.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1018903705269\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1018903705269.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,18]],"date-time":"2025-05-18T05:35:05Z","timestamp":1747546505000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1018903705269"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,3]]},"references-count":35,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[1997,3]]}},"alternative-id":["325415"],"URL":"https:\/\/doi.org\/10.1023\/a:1018903705269","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"type":"print","value":"1012-2443"},{"type":"electronic","value":"1573-7470"}],"subject":[],"published":{"date-parts":[[1997,3]]}}}