{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T11:15:34Z","timestamp":1773314134148,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540230243","type":"print"},{"value":"9783540301240","type":"electronic"}],"license":[{"start":{"date-parts":[[2004,1,1]],"date-time":"2004-01-01T00:00:00Z","timestamp":1072915200000},"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":[[2004]]},"DOI":"10.1007\/978-3-540-30124-0_29","type":"book-chapter","created":{"date-parts":[[2010,3,2]],"date-time":"2010-03-02T12:27:59Z","timestamp":1267532879000},"page":"370-384","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Logical Characterizations of PSPACE"],"prefix":"10.1007","author":[{"given":"David","family":"Richerby","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2004,9,9]]},"reference":[{"key":"29_CR1","first-page":"218","volume-title":"Proceedings of 9th ACM Symposium on Principles of Database Systems","author":"S. Abiteboul","year":"1990","unstructured":"Abiteboul, S., Simon, E., Vianu, V.: Non-deterministic languages to express deterministic transformations. In: Proceedings of 9th ACM Symposium on Principles of Database Systems, pp. 218\u2013229. ACM Press, New York (1990)"},{"key":"29_CR2","first-page":"71","volume-title":"Proceedings of 4th IEEE Annual Symposium on Logic in Computer Science","author":"S. Abiteboul","year":"1989","unstructured":"Abiteboul, S., Vianu, V.: Fixpoint extensions of first-order and datalog-like languages. In: Proceedings of 4th IEEE Annual Symposium on Logic in Computer Science, pp. 71\u201379. IEEE Computer Society Press, Los Alamitos (1989)"},{"issue":"3","key":"29_CR3","doi-asserted-by":"publisher","first-page":"1264","DOI":"10.2307\/2586700","volume":"65","author":"A. Blass","year":"2000","unstructured":"Blass, A., Gurevich, Y.: The logic of choice. Journal of Symbolic Logic\u00a065(3), 1264\u20131310 (2000)","journal-title":"Journal of Symbolic Logic"},{"issue":"2","key":"29_CR4","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1006\/inco.1998.2703","volume":"143","author":"A. Dawar","year":"1998","unstructured":"Dawar, A.: A restricted second order logic for finite structures. Information and Computation\u00a0143(2), 154\u2013174 (1998)","journal-title":"Information and Computation"},{"issue":"4","key":"29_CR5","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1093\/logcom\/13.4.503","volume":"13","author":"A. Dawar","year":"2003","unstructured":"Dawar, A., Richerby, D.M.: Fixed-point logics with nondeterministic choice. Journal of Logic and Computation\u00a013(4), 503\u2013530 (2003)","journal-title":"Journal of Logic and Computation"},{"key":"29_CR6","first-page":"25","volume-title":"Model-Theoretic Logics","author":"H.-D. Ebbinghaus","year":"1985","unstructured":"Ebbinghaus, H.-D.: Extended logics: The general framework. In: Barwise, J., Feferman, S. (eds.) Model-Theoretic Logics, pp. 25\u201376. Springer, Heidelberg (1985)"},{"key":"29_CR7","volume-title":"Finite Model Theory","author":"H.-D. Ebbinghaus","year":"1999","unstructured":"Ebbinghaus, H.-D., Flum, J.: Finite Model Theory, 2nd edn. Springer, Heidelberg (1999)","edition":"2"},{"key":"29_CR8","first-page":"43","volume-title":"Complexity of Computation","author":"R. Fagin","year":"1974","unstructured":"Fagin, R.: Generalized first-order spectra and polynomial-time recognizable sets. In: Karp, R. (ed.) Complexity of Computation. SIAM-AMS Proceedings, vol.\u00a07, pp. 43\u201373. SIAM-AMS, Philadelphia (1974)"},{"key":"29_CR9","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1002\/malq.19750210112","volume":"21","author":"R. Fagin","year":"1975","unstructured":"Fagin, R.: Monadic generalized spectra. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik\u00a021, 89\u201396 (1975)","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"issue":"1","key":"29_CR10","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1006\/inco.1998.2712","volume":"144","author":"F. Gire","year":"1998","unstructured":"Gire, F., Hoang, H.K.: An extension of fixpoint logic with a symmetrybased choice construct. Information and Computation\u00a0144(1), 40\u201365 (1998)","journal-title":"Information and Computation"},{"key":"29_CR11","volume-title":"Grundlagen der Mathematik","author":"D. Hilbert","year":"1939","unstructured":"Hilbert, D., Bernays, P.: Grundlagen der Mathematik, vol.\u00a02. Springer, Heidelberg (1939)"},{"issue":"1\u20133","key":"29_CR12","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/S0019-9958(84)80023-6","volume":"60","author":"D. Harel","year":"1984","unstructured":"Harel, D., Peleg, D.: On static logics, dynamic logics, and complexity classes. Information and Control\u00a060(1\u20133), 86\u2013102 (1984)","journal-title":"Information and Control"},{"issue":"1\u20133","key":"29_CR13","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/S0019-9958(86)80029-8","volume":"68","author":"N. Immerman","year":"1986","unstructured":"Immerman, N.: Relational queries computable in polynomial time. Information and Control\u00a068(1\u20133), 86\u2013104 (1986)","journal-title":"Information and Control"},{"issue":"4","key":"29_CR14","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"Immerman, N.: Logics that capture complexity classes. SIAM Journal of Computing\u00a016(4), 236\u2013244 (1987)","journal-title":"SIAM Journal of Computing"},{"issue":"5","key":"29_CR15","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"Immerman, N.: Nondeterministic space is closed under complementation. SIAM Journal of Computing\u00a017(5), 935\u2013938 (1988)","journal-title":"SIAM Journal of Computing"},{"issue":"2","key":"29_CR16","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1016\/0890-5401(92)90021-7","volume":"98","author":"P.G. Kolaitis","year":"1992","unstructured":"Kolaitis, P.G., Vardi, M.Y.: Infinitary logics and 0-1 laws. Information and Computation\u00a098(2), 258\u2013294 (1992)","journal-title":"Information and Computation"},{"issue":"4","key":"29_CR17","doi-asserted-by":"publisher","first-page":"1749","DOI":"10.2307\/2695073","volume":"65","author":"M. Otto","year":"2000","unstructured":"Otto, M.: Epsilon-logic is more expressive than first-order logic over finite structures. Journal of Symbolic Logic\u00a065(4), 1749\u20131757 (2000)","journal-title":"Journal of Symbolic Logic"},{"issue":"2","key":"29_CR18","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W.J. Savitch","year":"1970","unstructured":"Savitch, W.J.: Relationships between nondeterministic and deterministic tape complexities. J. Computer and System Sciences\u00a04(2), 177\u2013192 (1970)","journal-title":"J. Computer and System Sciences"},{"issue":"1","key":"29_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L.J. Stockmeyer","year":"1976","unstructured":"Stockmeyer, L.J.: The polynomial-time hierarchy. Theoretical Computer Science\u00a03(1), 1\u201322 (1976)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"29_CR20","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/BF00299636","volume":"26","author":"R. Szelepcs\u00e9nyi","year":"1988","unstructured":"Szelepcs\u00e9nyi, R.: The method of forced enumeration for nondeterministic automata. Acta Informatica\u00a026(3), 279\u2013284 (1988)","journal-title":"Acta Informatica"},{"key":"29_CR21","first-page":"569","volume":"70","author":"B.A. Trakhtenbrot","year":"1950","unstructured":"Trakhtenbrot, B.A.: Impossibility of an algorithm for the decision problem in finite classes. Doklady Akademii Nauk SSSR\u00a070, 569\u2013572 (1950), (In Russian; English translation: AMS Translations, Series 2, 23:1\u20135, 1963.)","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"29_CR22","first-page":"137","volume-title":"Proceedings of 14th ACM Symposium on Theory of Computing","author":"M.Y. Vardi","year":"1982","unstructured":"Vardi, M.Y.: Complexity of relational query languages. In: Proceedings of 14th ACM Symposium on Theory of Computing, pp. 137\u2013146. ACM Press, New York (1982)"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30124-0_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,22]],"date-time":"2020-01-22T08:06:49Z","timestamp":1579680409000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30124-0_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540230243","9783540301240"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30124-0_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004]]},"assertion":[{"value":"9 September 2004","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}