{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:22:45Z","timestamp":1725456165758},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540600176"},{"type":"electronic","value":"9783540494041"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/bfb0022260","type":"book-chapter","created":{"date-parts":[[2005,11,22]],"date-time":"2005-11-22T01:12:29Z","timestamp":1132621949000},"page":"242-248","source":"Crossref","is-referenced-by-count":1,"title":["Is first order contained in an initial segment of PTIME?"],"prefix":"10.1007","author":[{"given":"Alexei P.","family":"Stolboushkin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael A.","family":"Taitslin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,15]]},"reference":[{"key":"18_CR1","unstructured":"Aho, Alfred V., John E. Hopcroft, and Jeffrey D. Ullman, \u201cThe design and analysis of computer algorithms\u201d, Addison-Wesley Publ. Co., 1974, 1\u2013470."},{"key":"18_CR2","doi-asserted-by":"crossref","unstructured":"Aho, Alfred V., and Jeffrey D. Ullman, Universality of data retrieval languages, in: \u201cProceedings of the 6th ACM Symp. on Principles of Programming Languages (POPL)\u201d, 1979, 110\u2013117.","DOI":"10.1145\/567752.567763"},{"key":"18_CR3","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/BF01457985","volume":"86","author":"H. Behmann","year":"1922","unstructured":"Behmann, Heinrich, Beitr\u00e4ge zur Algebra der Logic, insbesondere zur Entscheidungproblem, Math. Ann., 86, 1922, 163\u2013229.","journal-title":"Math. Ann."},{"key":"18_CR4","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1016\/0022-0000(80)90032-X","volume":"25","author":"A. K. Chandra","year":"1980","unstructured":"Chandra, Ashok K., and David Harel, Structure and complexity of relational queries, J. Comput. Syst. Sci., 25, 1980, 156\u2013178.","journal-title":"J. Comput. Syst. Sci."},{"key":"18_CR5","first-page":"150","volume-title":"Bounded-arity hierarchies in fixed-point logics","author":"M. Grohe","year":"1994","unstructured":"Grohe, Martin, Bounded-arity hierarchies in fixed-point logics, in: \u201cProceedings of CSL '93. 1993 Annual Conference of the European Association for Computer Science Logic, Swansea, UK, 13\u201317 Sept. 1993)\u201d (Borger, E.; Gurevich, Y.; Meinke, K., Eds.), Springer-Verlag: Berlin, 1994. 150\u2013164."},{"key":"18_CR6","doi-asserted-by":"crossref","unstructured":"Gurevich, Yuri, Algebras of feasible functions, in: \u201c24th Symp. on Foundations of Computer Science (FOCS)\u201d, IEEE Computer Society Press, 1983, 210\u2013214.","DOI":"10.1109\/SFCS.1983.5"},{"key":"18_CR7","first-page":"1","volume-title":"Current Trends in Theoretical Computer Science","author":"Y. Gurevich","year":"1987","unstructured":"Gurevich, Yuri, Logic and the challenge of computer science, in: \u201cCurrent Trends in Theoretical Computer Science\u201d (Egon B\u00f6rger, Ed.), Computer Science Press: Rockville, Md., 1987, 1\u201357."},{"key":"18_CR8","volume-title":"A mathematical introduction to logic","author":"H. B. Enderton","year":"1972","unstructured":"Enderton, Herbert B., \u201cA mathematical introduction to logic\u201d, Academic Press: New York, 1972."},{"issue":"4","key":"18_CR9","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1070\/rm1965v020n04ABEH001188","volume":"20","author":"Y. L. Ershov","year":"1965","unstructured":"Ershov, Yuri L., Igor A. Lavrov, Asan D. Taimanov, and Michael A. Taitslin, Elementary theories, Russian Mathematical Surveys, 20:4, 1965, 35\u2013105.","journal-title":"Russian Mathematical Surveys"},{"key":"18_CR10","doi-asserted-by":"crossref","unstructured":"Hennie, F.C., and R.E. Stearns, Two tape simulation of multitape machines, J. ACM, 13:4, 533\u2013546.","DOI":"10.1145\/321356.321362"},{"key":"18_CR11","doi-asserted-by":"crossref","unstructured":"Immerman, Neil, Relational queries computable in polynomial time, in: \u201c14th ACM Symp. on Theory of Computing (STOC)\u201d, ACM, 1982, 147\u2013152.","DOI":"10.1145\/800070.802187"},{"key":"18_CR12","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"Immerman, Neil, Languages that capture complexity classes, S1AM J. Computing, 16, 1987, 760\u2013778.","journal-title":"S1AM J. Computing"},{"key":"18_CR13","first-page":"168","volume-title":"Implicit definability on finite structures and unambiguous computations","author":"P. G. Kolaitis","year":"1990","unstructured":"Kolaitis, Phokion G., Implicit definability on finite structures and unambiguous computations, in: \u201c5th IEEE Annu. Symp. on Logic in Computer Science (LICS)\u201d, IEEE Computer Society Press: Los Alamitos, CA, 1990, 168\u2013180."},{"key":"18_CR14","unstructured":"Livchak, Alexander B., The relational model for process control, in: \u201cAutomatic Documentation and Mathematical Linguistics 4\u201d, Moscow, 1983, 27\u201329."},{"key":"18_CR15","first-page":"489","volume":"23","author":"A. I. Maltsev","year":"1959","unstructured":"Maltsev, Anatoly I., Regular products of models, Izv. Acad. Nauk. SSSR, Ser. Mat., 23, 1959, 489\u2013502.","journal-title":"Izv. Acad. Nauk. SSSR, Ser. Mat."},{"key":"18_CR16","volume-title":"Elementary induction on abstract structures","author":"Y. N. Moschovakis","year":"1974","unstructured":"Moschovakis, Yiannis N., \u201cElementary induction on abstract structures\u201d, North-Holland\/Elsevier: Amsterdam\/New York, 1974, 218pp."},{"key":"18_CR17","first-page":"319","volume":"16","author":"V. Y. Sazonov","year":"1980","unstructured":"Sazonov, Valdimir Yu., Polinomial computability and recursivity in finite domains, Elektronische Informationsverarbeitung und Kybernetik, 16, 1980, 319\u2013323.","journal-title":"Elektronische Informationsverarbeitung und Kybernetik"},{"key":"18_CR18","first-page":"180","volume-title":"Cybernetics and Computing Technology","author":"A. P. Stolboushkin","year":"1986","unstructured":"Stolboushkin, Alexei P., and Michael A. Taitslin, Dynamic logics, in: \u201cCybernetics and Computing Technology\u201d (V.A. Mel'nikov, Ed.), Moscow: Nauka, 1986, 180\u2013230."},{"key":"18_CR19","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/0020-0190(76)90097-1","volume":"5","author":"L. Valiant","year":"1976","unstructured":"Valiant, L., Relative complexity of checking and evaluating, Information Processing, 5, 1976, 20\u201323.","journal-title":"Information Processing"},{"key":"18_CR20","doi-asserted-by":"crossref","unstructured":"Vardi, Moshe Y., Complexity of relational query languages, in: \u201c14th ACM Symp. on Theory of Computing\u201d, ACM, 1982, 137\u2013146.","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\/BFb0022260","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,10]],"date-time":"2020-04-10T22:43:29Z","timestamp":1586558609000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0022260"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540600176","9783540494041"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/bfb0022260","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}