{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:10:25Z","timestamp":1725455425915},"publisher-location":"Berlin\/Heidelberg","reference-count":24,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540167838"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0016242","type":"book-chapter","created":{"date-parts":[[2005,11,13]],"date-time":"2005-11-13T05:39:17Z","timestamp":1131860357000},"page":"177-198","source":"Crossref","is-referenced-by-count":6,"title":["Higher-order arrays and stacks in programming. An application of complexity theory to logics of programs"],"prefix":"10.1007","author":[{"given":"Jerzy","family":"Tiuryn","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"13_CR1","first-page":"48","volume":"140","author":"P. Berman","year":"1982","unstructured":"Berman, P., J.Y. Halpern and J. Tiuryn. On the power of nondeterminism in Dynamic Logic. In Proc. 9th ICALP Nielsen,M. and E.M.Schmidt (eds), LNCS 140, Springer-Verlag (1982), pp.48\u201360.","journal-title":"LNCS"},{"key":"13_CR2","unstructured":"Boehm,H., A.Demers, and J.Donahue. An informal description of Russel. Technical Report TR 80\u2013430, Computer Sci. Dept., Cornell University (1980)."},{"key":"13_CR3","first-page":"333","volume":"171","author":"E. B\u00f6rger","year":"1984","unstructured":"B\u00f6rger, E. Spectralproblem and completeness of logical decision problems. In Logic and Machines: Decision Problems and Complexity, Proceedings. B\u00f6rger,E., G.Hasenjaeger and D.R\u00f6dding (eds), LNCS 171, Springer-Verlag (1984), pp.333\u2013356.","journal-title":"LNCS"},{"key":"13_CR4","first-page":"1","volume":"173","author":"R. Burstall","year":"1984","unstructured":"Burstall, R. and B. Lampson. A Kernel Language for Abstract Data Types and Modules. In Semantics of Data Types, Proceedings. Kahn,G., D.B.Mac Queen and D.G.Plotkin (eds), LNCS 173, Springer-Verlag (1984), pp.1\u201350.","journal-title":"LNCS"},{"key":"13_CR5","unstructured":"Chang,C.C. and H.J.Keisler. Model Theory. North-Holland Publ. Co., (1973)."},{"issue":"1","key":"13_CR6","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1145\/322108.322121","volume":"26","author":"E.M. Clarke","year":"1979","unstructured":"Clarke, E.M. Programming Language Constructs for Which It Is Impossible to Obtain Good Hoare Axiom Systems. Journal of ACM 26, 1 (1979), pp.129\u2013147.","journal-title":"Journal of ACM"},{"key":"13_CR7","doi-asserted-by":"crossref","unstructured":"Engelfriet,J. Iterated Pushdown Automata and Complexity Classes.Proc. 15th ACM STOC, (1983), pp.365\u2013373.","DOI":"10.1145\/800061.808767"},{"key":"13_CR8","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/S0019-9958(84)80023-6","volume":"60","author":"D. Harel","year":"1984","unstructured":"Harel, D. and D. Peleg. On Static Logics, Dynamic Logics, and Complexity Classes. Information and Control 60 (1984), pp.86\u2013102.","journal-title":"Information and Control"},{"key":"13_CR9","first-page":"69","volume":"173","author":"J.G. Hook","year":"1984","unstructured":"Hook, J.G. Understanding Russel \u2014 a first attempt. In Semantics of Data Types, Proceedings. Kahn,G. D.B.Mac Queen and G.D.Plotkin (eds), LNCS 173, Springer-Verlag (1984), pp.69\u201385.","journal-title":"LNCS"},{"key":"13_CR10","unstructured":"Hopcroft,J.E. and J.D.Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley Publ. Co. (1979)."},{"key":"13_CR11","doi-asserted-by":"crossref","unstructured":"Immerman,N. Languages which Capture Complexity Classes. Proc. 15th ACM STOC (1983), pp.347\u2013354.","DOI":"10.1145\/800061.808765"},{"key":"13_CR12","unstructured":"Kowalczyk,W., D.Niwinski, and J.Tiuryn. A generalization of Cook's Auxiliary-Pushdown-Automata Theorem. To appear"},{"key":"13_CR13","first-page":"348","volume":"17","author":"R. Milner","year":"1978","unstructured":"Milner, R. A theory of type polymorphism. JCSS 17 (1978), pp.348\u2013375.","journal-title":"JCSS"},{"key":"13_CR14","unstructured":"Naur, P.(ed.) Revised report on the algorithmic language ALGOL 60. Comm. ACM 6, 4 (1963), pp.1\u201347."},{"key":"13_CR15","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1017\/S0022481200100076","volume":"17","author":"H. Sholz","year":"1952","unstructured":"Sholz, H. Ein ungel\u00f6stes Problem in der symbolischen Logik. The Journal of Symbolic Logic 17 (1952), p.160.","journal-title":"The Journal of Symbolic Logic"},{"key":"13_CR16","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., and M.A. Taitslin. Deterministic Dynamic Logic is strictly weaker than Dynamic Logic. Information and Control 57 (1983), pp.48\u201355.","journal-title":"Information and Control"},{"key":"13_CR17","unstructured":"Tiuryn,J., and P.Urzyczyn. Some relationships between Logics of Programs and Complexity Theory. Proc. 24th IEEE Symp. FOCS (1883), pp.180\u2013184."},{"key":"13_CR18","first-page":"535","volume":"176","author":"J. Tiuryn","year":"1984","unstructured":"Tiuryn, J., and P. Urzyczyn. Remarks on comparing expressive power of Logics of Programs. In Proc. MFCS 1984. Chytil,M. and V.Koubek (eds), LNCS 176, Springer-Verlag (1984), pp.535\u2013543.","journal-title":"LNCS"},{"key":"13_CR19","unstructured":"Tiuryn,J. An Introduction to First-Order Programming Logics. Technical Report, CS-84-126, Computer Sci. Dept., Washington State University (1984). To appear in Springer LNCS in 1986."},{"key":"13_CR20","first-page":"387","volume":"193","author":"J. Tiuryn","year":"1985","unstructured":"Tiuryn, J. A simple programming language with data types: Semantics and Verification. In Proc. Logics of Programs Conference 1985. Parikh,R. (ed.), LNCS193, Springer-Verlag (1985), pp.387\u2013405.","journal-title":"LNCS"},{"key":"13_CR21","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1016\/S0019-9958(83)80006-0","volume":"56","author":"P. Urzyczyn","year":"1983","unstructured":"Urzyczyn, P. A necessary and sufficient condition in order that a Herbrand Interpretation be expressive relative to recursive programs. Information and Control 56, (1983), pp.212\u2013219.","journal-title":"Information and Control"},{"key":"13_CR22","unstructured":"Reference manual for the Ada programming language. ANSI\/MIL-STD 1815A, United States Department of Defense, Washington D.C. (1983)."},{"key":"13_CR23","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF00265077","volume":"5","author":"A. Wijngaarden van","year":"1975","unstructured":"van Wijngaarden, A., et.al. Revised report on the algorithmic language ALGOL 68. Acta Informatica 5 (1975), pp.1\u2013236.","journal-title":"Acta Informatica"},{"key":"13_CR24","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/BF00264291","volume":"1","author":"N. Wirth","year":"1971","unstructured":"Wirth, N. The programming language PASCAL. Acta Informatica 1 (1971), pp.35\u201363.","journal-title":"Acta Informatica"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1986"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0016242.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T21:35:34Z","timestamp":1607549734000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0016242"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540167838"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/bfb0016242","relation":{},"subject":[]}}