{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:19:58Z","timestamp":1742617198575,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540601784"},{"type":"electronic","value":"9783540447207"}],"license":[{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60178-3_97","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:49:38Z","timestamp":1330278578000},"page":"447-462","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A constant-space sequential model of computation for first-order logic"],"prefix":"10.1007","author":[{"given":"Steven","family":"Lindell","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"22_CR1","first-page":"163","volume":"665","author":"E. Allender","year":"1993","unstructured":"E. Allender, Balc\u00e1zar, N.. Immerman \u201cA First-Order Isomorphism Theorem\u201d to appear in SIAM Journal on Computing. A preliminary version appeared in Proc. 10th Symposium on Theoretical Aspects of Computer Science, Springer-Verlag LNCS 665, pp. 163\u2013174, 1993.","journal-title":"Springer-Verlag LNCS"},{"key":"22_CR2","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/0020-0190(91)90015-A","volume":"40","author":"E. Allender","year":"1991","unstructured":"E. Allender, V. Gore \u201cRudimentary reductions revisited\u201d Information Processing Letters 40 89\u201395 (1991).","journal-title":"Information Processing Letters"},{"doi-asserted-by":"crossref","unstructured":"S. Buss, \u201cAlgorithms for Boolean Formula Evaluation and for Tree Contraction\u201d in Arithmetic, Proof Theory, and Computational Complexity, editors: Peter Clote and Jan Kraj\u00edc\u011bk, Oxford University Press, pp.95\u2013115, 1993.","key":"22_CR3","DOI":"10.1093\/oso\/9780198536901.003.0005"},{"doi-asserted-by":"crossref","unstructured":"D. Mix Barrington, K. Compton, H. Straubing, D. Th\u00e9rien \u201cRegular Languages in NC 1\u201d JCSS, June 1992 pp. 478\u2013499.","key":"22_CR4","DOI":"10.1016\/0022-0000(92)90014-A"},{"doi-asserted-by":"crossref","unstructured":"D. Mix Barrington, N. Immerman \u201cTime, Hardware, and Uniformity\u201d IEEE Structures, 1994 pp.176\u2013185.","key":"22_CR5","DOI":"10.1109\/SCT.1994.315806"},{"key":"22_CR6","first-page":"274","volume":"41","author":"D. M. Barrington","year":"1990","unstructured":"D. Mix Barrington, N. Immerman, H. Straubing \u201cOn Uniformity in NC 1\u201d JCSS 41, pp.274\u2013306 (1990).","journal-title":"JCSS"},{"doi-asserted-by":"crossref","unstructured":"P. Clote \u201cSequential, machine-independent characterizations of the parallel complexity classes AlogTIME, AC k, NC k and NC.\u201d in Feasible Mathematics, S. Buss and P. Scott editors, Birkh\u00e4user 1990.","key":"22_CR7","DOI":"10.1007\/978-1-4612-3466-1_4"},{"doi-asserted-by":"crossref","unstructured":"E. Dahlhaus, \u201cReduction to NP-complete problems by interpretations\u201d LNCS 171, Springer-Verlag, pp.357\u2013365, 1984.","key":"22_CR8","DOI":"10.1007\/3-540-13331-3_51"},{"issue":"No.2","key":"22_CR9","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1093\/logcom\/5.2.213","volume":"5","author":"A. Dawar","year":"1995","unstructured":"A. Dawar \u201cGeneralized Quantifiers and Logical Reducibilities\u201d Journal of Logic and Computation, Vol 5, No. 2, pp. 213\u2013226, 1995.","journal-title":"Journal of Logic and Computation"},{"unstructured":"H. Enderton, A Mathematical Introduction to Logic, Academic Press, 1972.","key":"22_CR10"},{"key":"22_CR11","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M. Furst","year":"1984","unstructured":"M. Furst, J.B. Saxe, M. Sipser \u201cParity, Circuits, and the Polynomial-time Hierarchy\u201d Math. Syst. Theory 17, pp. 13\u201327, 1984.","journal-title":"Math. Syst. Theory"},{"unstructured":"Y. Gurevich \u201cLogic and the Challenge of Computer Science\u201d in Trends in Theoretical Computer Science, Editor: Egon B\u00f6rger, Computer Science Press, 1988, pp.1\u201357.","key":"22_CR12"},{"unstructured":"J. W. Hong Computation: Computability, Similarity, and Duality Wiley 1986.","key":"22_CR13"},{"issue":"no.3","key":"22_CR14","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1137\/0218043","volume":"18","author":"N. Immerman","year":"1989","unstructured":"N. Immerman, \u201cExpressibility and Parallel Complexity\u201d SIAM Journal of Computing vol. 18 no. 3, June 1989, pp. 625\u2013638.","journal-title":"SIAM Journal of Computing"},{"issue":"1","key":"22_CR15","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1006\/inco.1995.1007","volume":"116","author":"N. Immerman","year":"1995","unstructured":"N. Immerman, S. Landau \u201cThe Complexity of Iterated Multiplication\u201d Information and Computation 116(1):103\u2013116, January 1995.","journal-title":"Information and Computation"},{"key":"22_CR16","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/0020-0190(94)00036-0","volume":"50","author":"S. Istrail","year":"1994","unstructured":"S. Istrail, D. Zivkovic \u201cBounded-width polynomial-size Boolean formulas compute exactly those functions in AC O\u201d Information Processing Letters 50, pp.211\u2013216, 1994.","journal-title":"Information Processing Letters"},{"unstructured":"S. Lindell, The Logical Complexity of Queries on Unordered Graphs, Ph.D. Dissertation, UCLA 1987.","key":"22_CR17"},{"unstructured":"S. Lindell, \u201cA Purely Logical Characterization of Circuit Uniformity\u201d IEEE Structure in Complexity Theory (1992) pp.185\u2013192.","key":"22_CR18"},{"doi-asserted-by":"crossref","unstructured":"H. Straubing, Finite Automata, Formal Logic, and Circuit Complexity, Birkh\u00e4user, 1994.","key":"22_CR19","DOI":"10.1007\/978-1-4612-0289-9"}],"container-title":["Lecture Notes in Computer Science","Logic and Computational Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60178-3_97","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:55:19Z","timestamp":1742597719000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60178-3_97"}},"subtitle":["Preliminary draft"],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540601784","9783540447207"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-60178-3_97","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]},"assertion":[{"value":"31 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}