{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,9]],"date-time":"2025-02-09T05:16:48Z","timestamp":1739078208267,"version":"3.37.0"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1998,12,1]],"date-time":"1998-12-01T00:00:00Z","timestamp":912470400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["New Gener Comput"],"published-print":{"date-parts":[[1998,12]]},"DOI":"10.1007\/bf03037430","type":"journal-article","created":{"date-parts":[[2009,4,24]],"date-time":"2009-04-24T02:51:25Z","timestamp":1240541485000},"page":"373-395","source":"Crossref","is-referenced-by-count":4,"title":["Non-determinism and weak constraints in Datalog"],"prefix":"10.1007","volume":"16","author":[{"given":"Sergio","family":"Greco","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"BF03037430_CR1","doi-asserted-by":"crossref","unstructured":"Abiteboul, S., Simon, E., and Vianu, V., \u201cNon-Deterministic Language to Compute Deterministic Transformation,\u201d inProc. of the Ninth ACM Symposium on Principles of Database Systems, pp. 218\u2013229, 1990.","DOI":"10.1145\/298514.298575"},{"issue":"1","key":"BF03037430_CR2","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/0022-0000(91)90032-Z","volume":"43","author":"S. Abiteboul","year":"1991","unstructured":"Abiteboul, S. and Vianu, V., \u201cDatalog Extensions for Databases Queries and Updates,\u201dJournal of Computer and System Science, 43, 1, pp. 62\u2013124, 1991.","journal-title":"Journal of Computer and System Science"},{"key":"BF03037430_CR3","unstructured":"Abiteboul, S., Hull, R., and Vianu, V.,Foundations of Databases, Addison-Wesley, 1994."},{"key":"BF03037430_CR4","doi-asserted-by":"crossref","unstructured":"Afrati, F., Cosmadakis, S.S., and Yannakakis, M., \u201cOn Datalog vs. Polynomial Time,\u201d inProc. of the Tenth ACM Symposium on Principles of Database Systems, pp. 13\u201325, 1991.","DOI":"10.1145\/113413.113415"},{"key":"BF03037430_CR5","doi-asserted-by":"crossref","unstructured":"Apt, C., Blair, H., and Walker, A., \u201cTowards a Theory of Declarative Knowledge,\u201d inProc. Workshop on Found. of Deductive Database and Logic Programming (Minker, ed.), pp. 89\u2013149, 1988.","DOI":"10.1016\/B978-0-934613-40-8.50006-3"},{"key":"BF03037430_CR6","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/BF02341854","volume":"8","author":"V. Baral","year":"1992","unstructured":"Baral, V. and Subrahmanian, V.S., \u201cStable and Extension Class Theory for Logic Programs and Default Logic,\u201dJournal of Automated Reasoning, 8, pp. 345\u2013366, 1992.","journal-title":"Journal of Automated Reasoning"},{"key":"BF03037430_CR7","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0022-0000(82)90012-5","volume":"25","author":"A. Chandra","year":"1982","unstructured":"Chandra, A. and Harel, D., \u201cStructures and Complexity of Relational Queries,\u201dJournal of Computer and System Science, 25, pp. 99\u2013128, 1982.","journal-title":"Journal of Computer and System Science"},{"key":"BF03037430_CR8","unstructured":"Dung, P., \u201cNegation as Hypotheses: An Abductive Foundation for Logic Programming,\u201d inProc. 8th Conf. on Logic Programming, pp. 3\u201317, 1991."},{"key":"BF03037430_CR9","doi-asserted-by":"crossref","unstructured":"Eiter, T., Gottlob, G., and Manila, H., \u201cExpressive Power and Complexity of Disjunctive Datalog,\u201dProc. ACM Symp. on Principles of Database Systems, pp. 267\u2013278, 1994.","DOI":"10.1007\/3-540-57802-1_5"},{"key":"BF03037430_CR10","unstructured":"Fagin, R., \u201cGeneralized First-Order Spectra and Polynomial-Time Recognizable Sets,\u201d inComplexity of Computation (R. Karp, ed.),SIAM-AMS Proc., 7, pp. 43\u201373, 1974."},{"key":"BF03037430_CR11","unstructured":"Gelfond, M. and Lifschitz, V., \u201cThe Stable Model Semantics of Logic Programming,\u201d inProc. of the Fifth Int. Conference on Logic Programming, pp. 1070\u20131080, 1988."},{"key":"BF03037430_CR12","doi-asserted-by":"crossref","unstructured":"Giannotti, F., Pedreschi, D., Sacc\u00e0, D., and Zaniolo, C., \u201cNondeterminism in Deductive Databases,\u201d inProc. 2nd Int. Conference on Deductive and Object-Oriented Databases, pp. 129\u2013146, 1991.","DOI":"10.1007\/3-540-55015-1_7"},{"key":"BF03037430_CR13","doi-asserted-by":"crossref","unstructured":"Greco, S., Zaniolo, C., and Ganguly, S., \u201cGreedy by Choice,\u201d inProc. of the Eleventh ACM Symposium on Principles of Database Systems, pp. 105\u2013163, 1992.","DOI":"10.1145\/137097.137836"},{"key":"BF03037430_CR14","doi-asserted-by":"crossref","unstructured":"Greco, S., Sacc\u00e0, D., and Zaniolo, C., \u201cDATALOG Queries with Stratified Negation and Choice: fromP toD P,\u201d inProc. of the Fifth Int. Conference on Database Theory, pp. 82\u201396, 1995.","DOI":"10.1007\/3-540-58907-4_8"},{"key":"BF03037430_CR15","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1023\/A:1018903705269","volume":"19","author":"S. Greco","year":"1997","unstructured":"Greco S. and Sacc\u00e0, D., \u201cPossible is Certain: Is Desiderable and Can be Expressive\u201d,Annals of Mathematics and Artificial Intelligence, 19, pp. 147\u2013168, 1997.","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"BF03037430_CR16","doi-asserted-by":"crossref","unstructured":"Immerman, N., \u201cLanguages that Capture Complexity Classes,\u201d inSIAM Journal of Computing, 16, 4, pp. 760\u2013778, 1987.","DOI":"10.1137\/0216051"},{"key":"BF03037430_CR17","doi-asserted-by":"crossref","unstructured":"Johnson, D.S., \u201cA Catalog of Complexity Classes,\u201d inHandbook of Theoretical Computer Science, Vol. A (J. Leewen, ed.), North-Holland, pp. 67\u2013161, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50007-2"},{"key":"BF03037430_CR18","unstructured":"Kanellakis, P.C., \u201cElements of Relational Databases Theory,\u201d inHandbook of Theoretical Computer Science, Vol B (J. Leewen, ed.), North-Holland, pp. 1075\u20131155, 1990."},{"key":"BF03037430_CR19","doi-asserted-by":"crossref","unstructured":"Kolaitis. P., \u201cThe Expressive Power of Stratified Logic Programs,\u201dInformation and Computation, 90, pp. 50\u201366, 1990.","DOI":"10.1016\/0890-5401(91)90059-B"},{"issue":"1","key":"BF03037430_CR20","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/0022-0000(91)90033-2","volume":"43","author":"P. Kolaitis","year":"1991","unstructured":"Kolaitis, P. and Papadimitriou, C., \u201cWhy Not Negation by Fixpoint,\u201dJournal of Computer and System Science, 43, 1, pp. 125\u2013144, 1991.","journal-title":"Journal of Computer and System Science"},{"key":"BF03037430_CR21","doi-asserted-by":"crossref","unstructured":"Krishnamurthy, R. and Naqvi, S., \u201cNon-Deterministic Choice in Datalog,\u201d inProc. of the Seventh ACM Symposium on Principles of Database Systems, 1988.","DOI":"10.1016\/B978-1-4832-1313-2.50038-X"},{"key":"BF03037430_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":"Lloyd, J.W.,Foundations of Logic Programming, Springer-Verlag, Berlin, 1987."},{"issue":"3","key":"BF03037430_CR23","doi-asserted-by":"crossref","first-page":"588","DOI":"10.1145\/116825.116836","volume":"38","author":"W. Marek","year":"1991","unstructured":"Marek, W. and Truszczynski, M., \u201cAutoepistemic Logic,\u201dJournal of ACM, 38, 3, pp. 588\u2013619, 1991.","journal-title":"Journal of ACM"},{"key":"BF03037430_CR24","unstructured":"Naqvi, S. and Tsur, S.,A Logic Language for Data and Knowledge Bases, Computer Science Press, 1989."},{"key":"BF03037430_CR25","unstructured":"Papadimitriou, C., \u201cA Note on the Expressive Power of Prolog,\u201d inBull of the EATCS, 26, pp. 21\u201323, 1985."},{"key":"BF03037430_CR26","unstructured":"Papadimitriou, C.,Computational Complexity, Addison-Wesley, 1994."},{"key":"BF03037430_CR27","doi-asserted-by":"crossref","first-page":"445","DOI":"10.3233\/FI-1990-13404","volume":"13","author":"T.C. Przymusinski","year":"1990","unstructured":"Przymusinski T.C., \u201cWell-Founded Semantics Coincides with Three-Valued Stable Semantics,\u201dFoundamenta Informaticae, 13, pp. 445\u2013463, 1990.","journal-title":"Foundamenta Informaticae"},{"key":"BF03037430_CR28","unstructured":"Ramakrisnhan, R., Srivastava, D., and Sudanshan, S., \u201cCORAL \u2014 Control, Relations and Logic,\u201d inProc. of 18th Int. Conference on Very Large Data Bases, 1992."},{"key":"BF03037430_CR29","doi-asserted-by":"crossref","unstructured":"Sacc\u00e0, D. and Zaniolo, C., \u201cStable Models and Non-Determinism in Logic Programs with Negation,\u201d inProc. of the Ninth ACM Symposium on principles of Database Systems, pp. 205\u2013217, 1990.","DOI":"10.1145\/298514.298572"},{"issue":"3","key":"BF03037430_CR30","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1006\/jcss.1997.1446","volume":"54","author":"D. Sacc\u00e0","year":"1997","unstructured":"Sacc\u00e0, D., \u201cThe Expressive Powers of Stable Models for Bound and Unbound DATALOG Queries,\u201dJournal of Computer and System Science, 54, 3, pp 441\u2013464, June 1997.","journal-title":"Journal of Computer and System Science"},{"issue":"1","key":"BF03037430_CR31","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1006\/jcss.1995.1053","volume":"51","author":"J.S. Schlipf","year":"1995","unstructured":"Schlipf, J.S., \u201cThe Expressive Powers of the Logic Programming Semantics,\u201dJournal of Computer and System Science, 51, 1, pp. 64\u201386, 1995.","journal-title":"Journal of Computer and System Science"},{"key":"BF03037430_CR32","unstructured":"Ullman, J.D.,Principles of Databases and Knowledge Base Systems, Computer Science Press, 1988.."},{"issue":"1","key":"BF03037430_CR33","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0743-1066(89)90032-0","volume":"6","author":"A. Gelder Van","year":"1989","unstructured":"Van Gelder, A., \u201cNegation as Failure Using Tight Derivations for General Logic Programs,\u201dJournal of Logic Programming, 6, 1, pp. 109\u2013133, 1989.","journal-title":"Journal of Logic Programming"},{"issue":"3","key":"BF03037430_CR34","doi-asserted-by":"crossref","first-page":"620","DOI":"10.1145\/116825.116838","volume":"38","author":"A. Gelder Van","year":"1991","unstructured":"Van Gelder, A., Ross, K.A. and Schlipf, J.S., \u201cThe Well-Founded Semantics for General Logic Programs,\u201dJournal of ACM, 38, 3, pp. 620\u2013650, 1991.","journal-title":"Journal of ACM"},{"key":"BF03037430_CR35","doi-asserted-by":"crossref","unstructured":"Vardi, M., \u201cThe Complexity of Relational Query Languages,\u201d inProc. of the 14th ACM Symposium on. Theory of Computing, pp. 137\u2013146, 1982.","DOI":"10.1145\/800070.802186"},{"key":"BF03037430_CR36","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1016\/S0022-0000(05)80053-4","volume":"19","author":"J. You","year":"1994","unstructured":"You, J. and Yuan, L.Y., \u201cA Three-Valued Semantics for Deductive Databases and Logic Programming,\u201dJournal of Computer and System Science, 19, pp. 334\u2013361, 1994.","journal-title":"Journal of Computer and System Science"}],"container-title":["New Generation Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF03037430.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF03037430\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF03037430","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,9]],"date-time":"2025-02-09T04:39:26Z","timestamp":1739075966000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF03037430"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,12]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1998,12]]}},"alternative-id":["BF03037430"],"URL":"https:\/\/doi.org\/10.1007\/bf03037430","relation":{},"ISSN":["0288-3635","1882-7055"],"issn-type":[{"type":"print","value":"0288-3635"},{"type":"electronic","value":"1882-7055"}],"subject":[],"published":{"date-parts":[[1998,12]]}}}