{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:49:47Z","timestamp":1725662987735},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540181705"},{"type":"electronic","value":"9783540477952"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1987]]},"DOI":"10.1007\/3-540-18170-9_181","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T19:29:57Z","timestamp":1330198197000},"page":"391-402","source":"Crossref","is-referenced-by-count":0,"title":["First steps towards a theory of complexity over more general data structures"],"prefix":"10.1007","author":[{"given":"Volker","family":"Sperschneider","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"33_CR1","unstructured":"Braun,H. (1986) Komplexit\u00e4t von Berechnungen auf der Datenstruktur der bin\u00e4ren W\u00f6rter mit Konkatenation, Interner Bericht der Fakult\u00e4t f\u00fcr Informatik der Universit\u00e4t Karlsruhe"},{"key":"33_CR2","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1007\/3-540-13331-3_31","volume-title":"Logic and Machines: Decision Problems and Complexity","author":"A. Blass","year":"1984","unstructured":"Blass, A., Gurevich, Y. (1984) Equivalence relations, invariants and normal forms, In:E. B\u00f6rger, G. Hasenjaeger, D. R\u00f6dding (eds), Logic and Machines: Decision Problems and Complexity, LNCS 171, Springer, Berlin Heidelberg New York, pp.24\u201342"},{"key":"33_CR3","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1007\/BFb0012756","volume-title":"Proceedings, Ninth Colloquium on Automata, Languages and Programming 82","author":"P. Berman","year":"1982","unstructured":"Berman, P., Halpern, J.Y., Tiuryn, J. (1982) On the power of non-determinism in Dynamic Logic, In: Proceedings, Ninth Colloquium on Automata, Languages and Programming 82, LNCS 140, Springer, Berlin Heidelberg New York, pp. 48\u201360"},{"key":"33_CR4","first-page":"496","volume-title":"Handbook of Philosophical Logic","author":"D. Harel","year":"1984","unstructured":"Harel, D. (1984) Dynamic Logic, In: D. Gabbey & F. Guenther (eds), Handbook of Philosophical Logic, Reidel Publishing, Dordrecht, pp. 496\u2013604"},{"key":"33_CR5","unstructured":"Hawrusik,F., Venkatamaran,K.N., Yasuhara,A. (1981) Classes of functions for computing on binary trees, STOC, pp. 19\u201327"},{"key":"33_CR6","doi-asserted-by":"crossref","unstructured":"Kfoury,A.J., Urzyczyn,P. (1985) Necessary and sufficient conditions for the universality of programming formalisms, Acta Informatica, Vol. 22(4)","DOI":"10.1007\/BF00288773"},{"key":"33_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(83)90013-0","volume":"25","author":"A.J. Kfoury","year":"1983","unstructured":"Kfoury,A.J. (1983) Definability by programs in first-order structures, Theoretical Computer Science 25, pp. 1\u201366","journal-title":"Theoretical Computer Science"},{"key":"33_CR8","unstructured":"Matchey,M., Young,P. (1978) An introduction to the general theory of algorithms, North-Holland"},{"key":"33_CR9","unstructured":"Sperschneider,V. (1985) Halbsymbolisches Rechnen als methodisches Werkzeug in der Komplexit\u00e4tstheorie auf Datenstrukturen, Habilitationsschrift, Universit\u00e4t Karlsruhe"},{"key":"33_CR10","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1016\/S0019-9958(83)80024-2","volume":"57","author":"A.P. Stolboushkin","year":"1983","unstructured":"Stolboushkin, A.P., Taitslin, M.A. (1983) Deterministic Dynamic Logic is strictly weaker than Dynamic Logic, Information and Control, Vol. 57, pp. 48\u201355","journal-title":"Information and Control"},{"key":"33_CR11","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1016\/S0019-9958(83)80024-2","volume":"57","author":"A.P. Stolboushkin","year":"1983","unstructured":"Stolboushkin, A.P. (1983) Regular Dynamic Logic is not interpretable in deterministic context-free Dynamic Logic, Information and Control, vol. 57, pp. 48\u201355","journal-title":"Information and Control"},{"key":"33_CR12","unstructured":"Tiuryn,J. (1986) A simplified proof of DDL<DL, To appear in Information and Control"},{"key":"33_CR13","doi-asserted-by":"crossref","unstructured":"Urzyczyn,P. (1981) The unwind property in certain algebras, Information and Control, Vol. 50","DOI":"10.1016\/S0019-9958(81)90163-7"}],"container-title":["Lecture Notes in Computer Science","Computation Theory and Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-18170-9_181.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T21:14:18Z","timestamp":1619558058000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-18170-9_181"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987]]},"ISBN":["9783540181705","9783540477952"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-18170-9_181","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1987]]}}}