{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T15:20:16Z","timestamp":1778858416487,"version":"3.51.4"},"reference-count":39,"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:1018955722107","type":"journal-article","created":{"date-parts":[[2003,2,19]],"date-time":"2003-02-19T22:07:13Z","timestamp":1045692433000},"page":"169-213","source":"Crossref","is-referenced-by-count":5,"title":["On non-determinism in machines and languages"],"prefix":"10.1007","volume":"19","author":[{"given":"St\u00e9phane","family":"Grumbach","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zo\u00e9","family":"Lacroix","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"325416_CR1","unstructured":"S. Abiteboul, R. Hull and V. Vianu, Foundations of Databases (Addison-Wesley, 1994)."},{"key":"325416_CR2","doi-asserted-by":"crossref","unstructured":"S. Abiteboul, E. Simon and V. Vianu, Non-deterministic languages to express deterministic transformations, in: Proc. 9th ACM Symp. on Principles of Database Systems (1990).","DOI":"10.1145\/298514.298575"},{"key":"325416_CR3","doi-asserted-by":"crossref","unstructured":"S. Abiteboul and V. Vianu, Fixpoint extensions of first-order logic and DATALOG like languages, in: Proc. 4th Symp. on Logic in Computer Science (1989) pp. 71\u201379.","DOI":"10.1109\/LICS.1989.39160"},{"key":"325416_CR4","doi-asserted-by":"crossref","unstructured":"S. Abiteboul and V. Vianu, Generic computation and its complexity, in: Proc. ACM Symp. on Theory of Computing, New Orleans (May 1991).","DOI":"10.1145\/103418.103444"},{"key":"325416_CR5","first-page":"151","volume":"3","author":"S. Abiteboul","year":"1991","unstructured":"S. Abiteboul and V. Vianu, Non-determinism in logic-based languages, Ann. of Math. and AI 3 (1991) 151\u2013186.","journal-title":"Ann. of Math. and AI"},{"key":"325416_CR6","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1016\/S1385-7258(53)50042-3","volume":"15","author":"E.W. Beth","year":"1953","unstructured":"E.W. Beth, On Padoa's method in the theory of definition, Indag. Math. 15 (1953) 330\u2013339.","journal-title":"Indag. Math."},{"key":"325416_CR7","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/S0019-9958(82)90439-9","volume":"55","author":"A. Blass","year":"1982","unstructured":"A. Blass and Y. Gurevich, On the unique satisfiability problem, Information and Control 55 (1982) 80\u201388.","journal-title":"Information and Control"},{"key":"325416_CR8","doi-asserted-by":"crossref","unstructured":"P. Van Emde Boas, Machine models and simulations, in: Handbook of Theorical Computer Science, Vol. A, ed. J. Van Leeuwen (North-Holland, 1990) p. 1\u201366.","DOI":"10.1016\/B978-0-444-88071-0.50006-0"},{"issue":"2","key":"325416_CR9","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1016\/0022-0000(80)90032-X","volume":"21","author":"A. Chandra","year":"1980","unstructured":"A. Chandra and D. Harel, Computable queries for relational databases, Journal of Computer and System Sciences 21(2) (Oct. 1980) 156\u2013178.","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"325416_CR10","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) (Aug. 1982) 99\u2013128.","journal-title":"Journal of Computer and System Sciences"},{"key":"325416_CR11","doi-asserted-by":"crossref","unstructured":"A. Dawar, L. Hella and P. Kolaitis, Implicit definability and infinitary logic in finite model theory, in: Proc. 22nd International Colloquium on Automata, Languages and Programming \u2014 ICALP '95 (1995).","DOI":"10.1007\/3-540-60084-1_110"},{"key":"325416_CR12","doi-asserted-by":"crossref","unstructured":"A. Ehrenfeucht, An application of games to the completeness problem for formalized theories, Fund. Math. 49 (1961).","DOI":"10.4064\/fm-49-2-129-141"},{"key":"325416_CR13","first-page":"43","volume":"7","author":"R. Fagin","year":"1974","unstructured":"R. Fagin, Generalized first-order spectra and polynomial-time recognizable sets, Complexity of Computations, SIAM-AMS Proceedings 7 (1974) pp. 43\u201373.","journal-title":"Complexity of Computations, SIAM-AMS Proceedings"},{"issue":"1","key":"325416_CR14","doi-asserted-by":"crossref","first-page":"50","DOI":"10.2307\/2272945","volume":"41","author":"R. Fagin","year":"1976","unstructured":"R. Fagin, Probabilities on finite models, Journal of Symbolic Logic 41(1) (1976) 50\u201358.","journal-title":"Journal of Symbolic Logic"},{"key":"325416_CR15","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0304-3975(93)90218-I","volume":"116","author":"R. Fagin","year":"1993","unstructured":"R. Fagin, Finite model theory \u2014 a personal perspective, Theoretical Computer Science 116 (1993) 3\u201331.","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"325416_CR16","first-page":"35","volume":"I","author":"R. Fra\u00efss\u00e9","year":"1954","unstructured":"R. Fra\u00efss\u00e9, Sur les classifications des syst\u00e8mes de relations, Publ. Sci. Univ Alger. I(1) (1954) 35\u2013182.","journal-title":"Publ. Sci. Univ Alger."},{"key":"325416_CR17","unstructured":"M. Garey and D. Johnson, Computers and Intractability. A Guide to the Theory of NP-Completeness (Freeman, 1979)."},{"key":"325416_CR18","doi-asserted-by":"crossref","unstructured":"S. Grumbach, Z. Lacroix and S. Lindell, Implicit definitions on finite structures, in: Computer Science Logic (Paderborn, 1995).","DOI":"10.1007\/3-540-61377-3_42"},{"key":"325416_CR19","doi-asserted-by":"crossref","unstructured":"F. Giannotti, D. Pedreschi, D. Sacc\u00e0 and C. Zaniolo, Non-determinsm in deductive databases, in: Proc. 2nd DOOD Conference (1991) pp. 129\u2013146.","DOI":"10.1007\/3-540-55015-1_7"},{"key":"325416_CR20","doi-asserted-by":"crossref","unstructured":"Y. Gurevich and S. Shelah, Fixed-point extensions of first-order logic, in: Proc IEEE Foundations of Computer Science (1985).","DOI":"10.1109\/SFCS.1985.27"},{"key":"325416_CR21","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1137\/0217018","volume":"17","author":"J. Grollmann","year":"1988","unstructured":"J. Grollmann and S. Selman, Complexity measures for public-key cryptosystems, SIAM J. Computing 17 (1988) 309\u2013335.","journal-title":"SIAM J. Computing"},{"key":"325416_CR22","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. Int. Conf. on Database Theory, eds. G. Gottlob and M. Vardi, Springer LNCS 893 (Prague, 1995) pp. 82\u201396.","DOI":"10.1007\/3-540-58907-4_8"},{"key":"325416_CR23","doi-asserted-by":"crossref","unstructured":"Y. Gurevich, Towards logic tailored for computational complexity, in: Computation and Proof Theory, eds. M. Richter et al., Lecture Notes in Mathematics 1104 (1984) pp. 175\u2013216.","DOI":"10.1007\/BFb0099486"},{"key":"325416_CR24","unstructured":"Y. Gurevich, Logic and the challenge of computer science, in: Current Trends in Theoretical Computer Science, ed. E. Borger (Computer Science Press, 1988) pp. 1\u201357."},{"key":"325416_CR25","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0304-3975(88)90022-9","volume":"58","author":"J. Hartamis","year":"1988","unstructured":"J. Hartamis and L.A. Hemachandra, Complexity classes without machines: on complete languages for up, Theoretical Computer Science 58 (1988) 129\u2013142.","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"325416_CR26","doi-asserted-by":"crossref","first-page":"761","DOI":"10.1145\/1634.1886","volume":"31","author":"T. Imielinski","year":"1984","unstructured":"T. Imielinski and W. Lipski, Incomplete information in relational databases, J. ACM 31(4) (1984) 761\u2013791.","journal-title":"J. ACM"},{"key":"325416_CR27","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/S0019-9958(86)80029-8","volume":"68","author":"N. Immerman","year":"1986","unstructured":"N. Immerman, Relational queries computable in polynomial time, Inf. and Control 68 (1986) 86\u2013104.","journal-title":"Inf. and Control"},{"key":"325416_CR28","doi-asserted-by":"crossref","unstructured":"D.S. Johnson, A catalog of complexity classes, in: Handbook of Theorical Computer Science, Vol. A, ed. J. Van Leeuwen (North-Holland, 1990) pp. 67\u2013162.","DOI":"10.1016\/B978-0-444-88071-0.50007-2"},{"key":"325416_CR29","doi-asserted-by":"crossref","unstructured":"P. Kanellakis, Elements of relational database theory, in: Handbook of Theorical Computer Science, Vol. B, ed. J. Van Leeuwen (North-Holland, 1990) pp. 1073\u20131156.","DOI":"10.1016\/B978-0-444-88074-1.50022-6"},{"key":"325416_CR30","unstructured":"P. Kolaitis, Implicit definability on finite structures and unambiguous computations, in: Proc. 5th Symp. of Logic in Computer Science (1990)."},{"key":"325416_CR31","doi-asserted-by":"crossref","unstructured":"R. Karp and V. Ramachandran, Parallel algorithms for shared memory machines, in: Handbook of Theorical Computer Science, Vol. A, ed. J. Van Leeuwen (North-Holland, 1990) pp. 869\u2013941.","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"key":"325416_CR32","unstructured":"Z. Lacroix, Bases de Donn\u00e9es: des Relations Implicites aux Relations Contraintes, Ph.D. Thesis, Universit\u00e9 Paris-Sud (1996)."},{"key":"325416_CR33","doi-asserted-by":"crossref","unstructured":"C.H. Papadimitriou and M. Yannakakis, The complexity of facets (and some facets of complexity), in: Proc. of the 14th Annual ACM Symposium on Theory of Computing, San Francisco (1982).","DOI":"10.1145\/800070.802199"},{"key":"325416_CR34","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1016\/0022-0000(84)90068-0","volume":"28","author":"C.H. Papadimitriou","year":"1984","unstructured":"C.H. Papadimitriou and M. Yannakakis, The complexity of facets (and some facets of complexity), Journal of Computer and System Sciences 28 (1984) 244\u2013259.","journal-title":"Journal of Computer and System Sciences"},{"key":"325416_CR35","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1016\/S0022-0000(05)80009-1","volume":"48","author":"A.L. Selman","year":"1994","unstructured":"A.L. Selman, A taxonomy of complexity classes of functions, Journal of Computer and System Sciences 48 (1994) 357\u2013381.","journal-title":"Journal of Computer and System Sciences"},{"key":"325416_CR36","doi-asserted-by":"crossref","unstructured":"D. Sacc\u00e0 and C. Zaniolo, Stable models and non-determinism in logic programs with negation, in: Proc. 9th ACM Symp. on Principles of Database Systems (1990) pp. 205\u2013217.","DOI":"10.1145\/298514.298572"},{"key":"325416_CR37","first-page":"569","volume":"70","author":"B.A. Trakhtenbrot","year":"1950","unstructured":"B.A. Trakhtenbrot, Impossibility of an algorithm for the decision problem in finite classes, Doklady Akademii Nauk SSSR 70 (1950) 569\u2013572.","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"325416_CR38","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/0020-0190(76)90097-1","volume":"5","author":"L. Valiant","year":"1976","unstructured":"L. Valiant, Relative complexity of checking and evaluating, Information Processing 5 (1976) 20\u201323.","journal-title":"Information Processing"},{"key":"325416_CR39","doi-asserted-by":"crossref","unstructured":"M. Vardi, The complexity of relational query languages, in: Proc. 14th ACM Symp. on Theory of Computing (1982) pp. 137\u2013146.","DOI":"10.1145\/800070.802186"}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1018955722107.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1018955722107\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1018955722107.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,18]],"date-time":"2025-05-18T05:35:53Z","timestamp":1747546553000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1018955722107"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,3]]},"references-count":39,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[1997,3]]}},"alternative-id":["325416"],"URL":"https:\/\/doi.org\/10.1023\/a:1018955722107","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"value":"1012-2443","type":"print"},{"value":"1573-7470","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,3]]}}}