{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,18]],"date-time":"2025-05-18T05:42:11Z","timestamp":1747546931867,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540613770"},{"type":"electronic","value":"9783540685074"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61377-3_42","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:35:47Z","timestamp":1330292147000},"page":"252-265","source":"Crossref","is-referenced-by-count":4,"title":["Generalized implicit definitions on finite structures"],"prefix":"10.1007","author":[{"given":"St\u00e9phane","family":"Grumbach","sequence":"first","affiliation":[]},{"given":"Zo\u00e9","family":"Lacroix","sequence":"additional","affiliation":[]},{"given":"Steven","family":"Lindell","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"15_CR1","doi-asserted-by":"crossref","unstructured":"M. Ajtai and Y. Gurevich. Datalog vs. first-order logic. In 30th IEEE Symp. on Foundations of Computer Science, pages 142\u2013146, 1989.","DOI":"10.1109\/SFCS.1989.63469"},{"key":"15_CR2","unstructured":"S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1994."},{"key":"15_CR3","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":"15_CR4","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:330\u2013339, 1953.","journal-title":"Indag. Math."},{"issue":"1","key":"15_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):99\u2013128, Aug. 1982.","journal-title":"Journal of Computer and System Sciences"},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"A. Dawar, L. Hella and Ph.G. Kolaitis. Implicit definability and infinitary logic in finite model theory. Proc. 22nd International Colloquium on Automata, Languages and Programming \u2014 ICALP 95, Lecture Notes in Computer Science, Springer-Verlag, to appear.","DOI":"10.1007\/3-540-60084-1_110"},{"key":"15_CR7","doi-asserted-by":"crossref","first-page":"129","DOI":"10.4064\/fm-49-2-129-141","volume":"49","author":"A. Ehrenfeucht","year":"1961","unstructured":"A. Ehrenfeucht. An application of games to the completness problem for formalized theories. Fund. Math. 49:129\u2013141, 1961.","journal-title":"Fund. Math."},{"key":"15_CR8","unstructured":"R. Fagin. Generalized first-order spectra and polynomial-time recognizable sets. Complexity of Computations, SIAM-AMS Proceedings 7, pages 43\u201373, 1974."},{"key":"15_CR9","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1002\/malq.19750210112","volume":"21","author":"R. Fagin","year":"1975","unstructured":"R. Fagin. Monadic generalized spectra. Zeitschrift f\u00fcr Math. Logik 21:89\u201396, 1975.","journal-title":"Zeitschrift f\u00fcr Math. Logik"},{"key":"15_CR10","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1017\/S0022481200051756","volume":"41","author":"R. Fagin","year":"1976","unstructured":"R. Fagin. Probabilities on finite models. Journal of Symbolic Logic 41:50\u201358, 1976.","journal-title":"Journal of Symbolic Logic"},{"key":"15_CR11","first-page":"35","volume":"1","author":"R. Fra\u00efsse","year":"1954","unstructured":"R. Fra\u00efsse. Sur quelques classifications des syst\u00e8mes de relations. Publications Scientifiques de l'Universit\u00e9 d'Alger, S\u00e9rie A 1:35\u2013182, 1954.","journal-title":"Publications Scientifiques de l'Universit\u00e9 d'Alger, S\u00e9rie A"},{"key":"15_CR12","doi-asserted-by":"crossref","unstructured":"Y. Gurevich. Computation and Proof Theory (M. Richter et al. Ed.), chapter Towards Logic tailored for Computational Complexity, pages 175\u2013216. Lecture Notes in Mathematics, 1104, 1984.","DOI":"10.1007\/BFb0099486"},{"key":"15_CR13","unstructured":"Y. Gurevich. Current Trends in Theoretical Computer Science, E. Borger Ed., chapter Logic and the Challenge of Computer Science, pages 1\u201357. Computer Science Press, 1988."},{"key":"15_CR14","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1007\/3-540-58907-4_8","volume":"893","author":"S. Greco","year":"1995","unstructured":"S. Greco D. Sacca and C. Zaniolo. DATALOG Queries with Stratified Negation and Choice: from P to D p. In Proc. ICDT'95, Springer Lecture Notes in Computer Science 893, 82\u201396, 1995.","journal-title":"Springer Lecture Notes in Computer Science"},{"key":"15_CR15","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:86\u2013104, 1986.","journal-title":"Inf. and Control"},{"key":"15_CR16","doi-asserted-by":"crossref","unstructured":"P. Kolaitis. Implicit definability on finite structures and unambiguous computations. In Proc. 5th Symp. of Logic in Computer Science, 1990.","DOI":"10.1109\/LICS.1990.113743"},{"key":"15_CR17","unstructured":"S. Lindell. The Logical Complexity of Queries on Unordered Graphs. Ph.D. thesis, University of California at Los Angeles, 1987."},{"key":"15_CR18","unstructured":"Y. N. Moschovakis. Elementary Induction on Abstract Structures. North Holland, 1974."},{"key":"15_CR19","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 Akademie Nauk SSSR, 70:569\u2013572, 1950.","journal-title":"Doklady Akademie Nauk SSSR"},{"key":"15_CR20","doi-asserted-by":"crossref","unstructured":"J.S. Schlipf. The Expressive Powers of the Logic Programming Semantics. In Proc. 9th ACM Symp. on Principles of Database Systems, 196\u2013204, 1990.","DOI":"10.1145\/298514.298564"},{"key":"15_CR21","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, 205\u2013217, 1990.","DOI":"10.1145\/298514.298572"},{"key":"15_CR22","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:20\u201323, 1976.","journal-title":"Information Processing"},{"key":"15_CR23","doi-asserted-by":"crossref","unstructured":"M. Vardi. The complexity of relational query languages. In Proc. 14th ACM Symp. on Theory of Computing, pages 137\u2013146, 1982.","DOI":"10.1145\/800070.802186"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61377-3_42.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:18:31Z","timestamp":1742599111000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61377-3_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540613770","9783540685074"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-61377-3_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}