{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T00:30:24Z","timestamp":1675125024304},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2009,9,3]],"date-time":"2009-09-03T00:00:00Z","timestamp":1251936000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2009,11]]},"DOI":"10.1007\/s00236-009-0103-x","type":"journal-article","created":{"date-parts":[[2009,9,2]],"date-time":"2009-09-02T03:28:23Z","timestamp":1251862103000},"page":"509-531","source":"Crossref","is-referenced-by-count":2,"title":["On the power of deep pushdown stacks"],"prefix":"10.1007","volume":"46","author":[{"given":"Argimiro Arratia","family":"Quesada","sequence":"first","affiliation":[]},{"given":"Iain A.","family":"Stewart","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,9,3]]},"reference":[{"key":"103_CR1","doi-asserted-by":"crossref","first-page":"915","DOI":"10.1093\/logcom\/9.6.915","volume":"9","author":"A.A. Arratia-Quesada","year":"1999","unstructured":"Arratia-Quesada A.A., Chauhan S.R., Stewart I.A.: Hierarchies in classes of program schemes. J. Logic. Comput. 9, 915\u2013957 (1999)","journal-title":"J. Logic. Comput."},{"key":"103_CR2","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1137\/0201006","volume":"1","author":"R. Constable","year":"1972","unstructured":"Constable R., Gries D.: On classes of program schemata. SIAM J. Comput. 1, 66\u2013118 (1972)","journal-title":"SIAM J. Comput."},{"key":"103_CR3","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/321623.321625","volume":"18","author":"S.A. Cook","year":"1971","unstructured":"Cook S.A.: Characterizations of pushdown pmachines in terms of time-bounded computers. J. Assoc. Comput. Mach. 18, 4\u201318 (1971)","journal-title":"J. Assoc. Comput. Mach."},{"key":"103_CR4","doi-asserted-by":"crossref","unstructured":"Dahlhaus, H.: Reduction to NP-complete problems by interpretations. In: B\u00f6rger, E., Hasenjaeger, G. (eds.) Proceedings of Logic and Machines: Decision Problems and Complexity, Lecture Notes in Computer Science, vol. 171, pp. 357\u2013365. Springer, Berlin (1984)","DOI":"10.1007\/3-540-13331-3_51"},{"key":"103_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03182-7","volume-title":"Finite Model Theory","author":"H.-D. Ebbinghaus","year":"1995","unstructured":"Ebbinghaus H.-D., Flum J.: Finite Model Theory. Springer-Verlag, Berlin (1995)"},{"key":"103_CR6","first-page":"361","volume-title":"Logic Colloquium 1969","author":"H. Friedman","year":"1971","unstructured":"Friedman H.: Algorithmic procedures, generalized turing algorithms and elementary recursion theory. In: Gandy, R.O., Yates, C.M.E. (eds) Logic Colloquium 1969, pp. 361\u2013390. North-Holland, Amsterdam (1971)"},{"key":"103_CR7","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1137\/0304034","volume":"4","author":"S. Ginsberg","year":"1968","unstructured":"Ginsberg S., Spanier E.: Finite-turn pushdown automata. SIAM J. Control 4, 429\u2013453 (1968)","journal-title":"SIAM J. Control"},{"key":"103_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., Peleg D.: On static logics, dynamic logics, and complexity classes. Inf. Control 60, 86\u2013102 (1984)","journal-title":"Inf. Control"},{"key":"103_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0539-5","volume-title":"Descriptive Complexity","author":"N. Immerman","year":"1999","unstructured":"Immerman N.: Descriptive Complexity. Springer, Berlin (1999)"},{"key":"103_CR10","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1145\/322003.322016","volume":"24","author":"N.D. Jones","year":"1977","unstructured":"Jones N.D., Muchnik S.S.: Even simple programs are hard to analyze. J. Assoc. Comput. Mach. 24, 338\u2013350 (1977)","journal-title":"J. Assoc. Comput. Mach."},{"key":"103_CR11","doi-asserted-by":"crossref","first-page":"492","DOI":"10.1016\/S0022-0000(70)80045-9","volume":"4","author":"T. Kasai","year":"1970","unstructured":"Kasai T.: An hierarchy between context-free and context-sensitive languages. J. Comput. Syst. Sci. 4, 492\u2013508 (1970)","journal-title":"J. Comput. Syst. Sci."},{"key":"103_CR12","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-07003-1","volume-title":"Elements of Finite Model Theory","author":"L. Libkin","year":"2004","unstructured":"Libkin L.: Elements of Finite Model Theory. Springer, Berlin (2004)"},{"key":"103_CR13","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4471-0501-5","volume-title":"Automata and Languages: Theory and Applications","author":"A. Meduna","year":"2000","unstructured":"Meduna A.: Automata and Languages: Theory and Applications. Springer, Berlin (2000)"},{"key":"103_CR14","doi-asserted-by":"crossref","first-page":"679","DOI":"10.1080\/0020716031000070616","volume":"80","author":"A. Meduna","year":"2003","unstructured":"Meduna A.: Simultaneously one-turn two-pushdown automata. Int. J. Comput. Math. 80, 679\u2013687 (2003)","journal-title":"Int. J. Comput. Math."},{"key":"103_CR15","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1007\/s00236-006-0005-0","volume":"42","author":"A. Meduna","year":"2006","unstructured":"Meduna A.: Deep pushdown automata. Acta. Informatica. 42, 541\u2013552 (2006)","journal-title":"Acta. Informatica."},{"key":"103_CR16","unstructured":"Paterson, M., Hewitt, N.: Comparative schematology, Record of Project MAC Conference on Concurrent Systems and Parallel Computation, pp. 119\u2013128. ACM Press, New York (1970)"},{"key":"103_CR17","doi-asserted-by":"crossref","unstructured":"Spector, L., Klein, J., Keijzer, M.: The Push3 execution stack and the evolution of control. In: Beyer, H.-G., O\u2019Reilly, U.-M. (eds.) Proceedings of Genetic and Evolutionary Computation Conference, pp. 1689\u20131696. ACM Press, New York (2005)","DOI":"10.1145\/1068009.1068292"},{"key":"103_CR18","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/0022-0000(92)90043-I","volume":"45","author":"I.A. Stewart","year":"1992","unstructured":"Stewart I.A.: Using the Hamiltonian path operator to capture NP. J. Comput. Syst. Sci. 45, 127\u2013151 (1992)","journal-title":"J. Comput. Syst. Sci."},{"key":"103_CR19","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/S0304-3975(01)00183-9","volume":"275","author":"I.A. Stewart","year":"2002","unstructured":"Stewart I.A.: Program schemes, arrays, Lindstr\u00f6m quantifiers and zero-one laws. Theor. Comput. Sci. 275, 283\u2013310 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"103_CR20","first-page":"40","volume":"6","author":"I.A. Stewart","year":"2003","unstructured":"Stewart I.A.: Using program schemes to logically capture polynomial-time on certain classes of structures. Lond. Math. Soc. J. Comput. Math. 6, 40\u201367 (2003)","journal-title":"Lond. Math. Soc. J. Comput. Math."},{"key":"103_CR21","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1093\/logcom\/exn025","volume":"19","author":"I.A. Stewart","year":"2009","unstructured":"Stewart I.A.: Logical and complexity-theoretic aspects of models of computation with restricted access to arrays. J. Logic Comput. 19, 217\u2013242 (2009)","journal-title":"J. Logic Comput."},{"key":"103_CR22","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/0304-3975(88)90052-7","volume":"60","author":"J. Tiuryn","year":"1988","unstructured":"Tiuryn J., Urzyczyn P.: Some relationships between logics of programs and complexity theory. Theor. Comput. Sci. 60, 83\u2013108 (1988)","journal-title":"Theor. Comput. Sci."},{"key":"103_CR23","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/S0019-9958(74)90839-0","volume":"25","author":"L.G. Valiant","year":"1974","unstructured":"Valiant L.G.: The equivalence problem for deterministic finite-turn pushdown automata. Inf. Control 25, 123\u2013133 (1974)","journal-title":"Inf. Control"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-009-0103-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00236-009-0103-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-009-0103-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T13:41:55Z","timestamp":1558705315000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00236-009-0103-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9,3]]},"references-count":23,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2009,11]]}},"alternative-id":["103"],"URL":"https:\/\/doi.org\/10.1007\/s00236-009-0103-x","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,9,3]]}}}