{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,5,3]],"date-time":"2023-05-03T07:40:13Z","timestamp":1683099613717},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1985,12,1]],"date-time":"1985-12-01T00:00:00Z","timestamp":502243200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Systems Theory"],"published-print":{"date-parts":[[1985,12]]},"DOI":"10.1007\/bf01699468","type":"journal-article","created":{"date-parts":[[2005,5,15]],"date-time":"2005-05-15T07:15:04Z","timestamp":1116141304000},"page":"171-187","source":"Crossref","is-referenced-by-count":30,"title":["Universal quantifiers and time complexity of random access machines"],"prefix":"10.1007","volume":"18","author":[{"given":"Etienne","family":"Grandjean","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"BF01699468_CR1","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A. K. Chandra","year":"1981","unstructured":"A. K. Chandra, D. C. Kozen and L. J. Stockmeyer, Alternation,J. Assoc. Comput. Mach. 28 (1981) 1, 114\u2013133.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01699468_CR2","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/S0022-0000(73)80028-5","volume":"7","author":"S. A. Cook","year":"1973","unstructured":"S. A. Cook, A hierarchy for nondeterministic time complexity,J. Comput. Systems Sci. 7 (1973), 343\u2013353.","journal-title":"J. Comput. Systems Sci."},{"key":"BF01699468_CR3","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1016\/S0022-0000(73)80029-7","volume":"7","author":"S. A. Cook","year":"1973","unstructured":"S. A. Cook and R. A. Reckhow, Time bounded Random Access Machines,J. Comput. Systems Sci. 7 (1973), 354\u2013375.","journal-title":"J. Comput. Systems Sci."},{"key":"BF01699468_CR4","unstructured":"R. Fagin, Generalized first-order spectra and polynomial-time recognizable sets,Complexity of Computations, R. M. Karp ed., Amer. Math. Soc., Providence, (1974), 43\u201373."},{"key":"BF01699468_CR5","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1002\/malq.19750210117","volume":"21","author":"R. Fagin","year":"1975","unstructured":"R. Fagin, A spectrum hierarchy,Z. Math. Logik. Grundlag. Math. 21 (1975), 123\u2013134.","journal-title":"Z. Math. Logik. Grundlag. Math."},{"key":"BF01699468_CR6","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1137\/0213025","volume":"13","author":"E. Grandjean","year":"1984","unstructured":"E. Grandjean, The spectra of first-order sentences and computational complexity,SIAM J. Comput. 13 (1984), 356\u2013373.","journal-title":"SIAM J. Comput."},{"key":"BF01699468_CR7","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1016\/0022-0000(81)90039-8","volume":"22","author":"N. Immerman","year":"1981","unstructured":"N. Immerman, Number of quantifiers is better than number of tape cells,J. Comput. Systems Sci. 22 (1981), 384\u2013406.","journal-title":"J. Comput. Systems Sci."},{"key":"BF01699468_CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0022-0000(82)90011-3","volume":"25","author":"N. Immerman","year":"1982","unstructured":"N. Immerman, Upper and lower bounds for first-order expressibility,J. Comput. Systems Sci. 25, 1 (1982).","journal-title":"J. Comput. Systems Sci."},{"key":"BF01699468_CR9","doi-asserted-by":"crossref","unstructured":"N. Immerman, Languages which capture complexity classes, 15th ACM SIGACT Symp. (1983), 1\u201316.","DOI":"10.1145\/800061.808765"},{"key":"BF01699468_CR10","doi-asserted-by":"crossref","first-page":"139","DOI":"10.2307\/2272354","volume":"39","author":"N. D. Jones","year":"1974","unstructured":"N. D. Jones and A. L. Selman, Turing machines and the spectra of first-order formulas with equality,J. Symb. Logic 39 (1974), 139\u2013150.","journal-title":"J. Symb. Logic"},{"key":"BF01699468_CR11","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/0022-0000(80)90027-6","volume":"21","author":"H. R. Lewis","year":"1980","unstructured":"H. R. Lewis, Complexity results for classes of quantificational formulas,J. Comput. Systems Sci. 21 (1980), 317\u2013353.","journal-title":"J. Comput. Systems Sci."},{"key":"BF01699468_CR12","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1002\/malq.19770233608","volume":"23","author":"L. Lov\u00e1sz","year":"1977","unstructured":"L. Lov\u00e1sz and P. G\u00e1cs, Some remarks on generalized spectra,Z. Math. Logik. Grundlag. Math. 23 (1977), 547\u2013553.","journal-title":"Z. Math. Logik. Grundlag. Math."},{"key":"BF01699468_CR13","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF01786976","volume":"15","author":"J. F. Lynch","year":"1982","unstructured":"J. F. Lynch, Complexity classes and theories of finite models,Mach. Systems Theory 15 (1982), 127\u2013144.","journal-title":"Mach. Systems Theory"},{"key":"BF01699468_CR14","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1007\/3-540-06841-4_67","volume-title":"2nd Int. Colloq. Automata Languages Programming","author":"B. Monien","year":"1974","unstructured":"B. Monien, Characterizations of time-bounded computations by limited primitive recursion,2nd Int. Colloq. Automata Languages Programming, Springer, Berlin (1974), 280\u2013293."},{"key":"BF01699468_CR15","doi-asserted-by":"crossref","unstructured":"B. Monien, About the derivation languages of grammars and machines,4th Int. Colloq. Automata Languages Programming, (1977), 337\u2013351.","DOI":"10.1007\/3-540-08342-1_26"},{"key":"BF01699468_CR16","first-page":"395","volume":"16","author":"P. Pukl\u00e1k","year":"1975","unstructured":"P. Pukl\u00e1k, The observational predicate calculus and complexity of computations,Comment. Math. Univ. Carolin. 16 (1975), 395\u2013398.","journal-title":"Comment. Math. Univ. Carolin."},{"key":"BF01699468_CR17","doi-asserted-by":"crossref","unstructured":"B. Scarpellini, Lower bound results on lengths of second order formulas (1984), preprint.","DOI":"10.1016\/0168-0072(85)90034-X"},{"key":"BF01699468_CR18","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1137\/0209036","volume":"9","author":"A. Sch\u00f6nhage","year":"1980","unstructured":"A. Sch\u00f6nhage, Storage Modification Machines,SIAM J. Comput. 9 (1980), 490\u2013508.","journal-title":"SIAM J. Comput."},{"key":"BF01699468_CR19","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1145\/322047.322061","volume":"25","author":"J. I. Seiferas","year":"1978","unstructured":"J. I. Seiferas, M. J. Fisher and A. R. Meyer, Separating nondeterministic time complexity classes,J. Assoc. Comput. Mach. 25 (1978), 146\u2013167.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01699468_CR20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. J. Stockmeyer","year":"1976","unstructured":"L. J. Stockmeyer, The polynomial-time hierarchy,Theoret. Comput. Sci. 3 (1976), 1\u201322.","journal-title":"Theoret. Comput. Sci."},{"key":"BF01699468_CR21","doi-asserted-by":"crossref","unstructured":"R. Weicker, Turing machines with associative memory access,2nd Int. Colloq. Automata Languages Programming (1974), 458\u2013472.","DOI":"10.1007\/978-3-662-21545-6_35"}],"container-title":["Mathematical Systems Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01699468.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01699468\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01699468","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,3]],"date-time":"2023-05-03T06:58:49Z","timestamp":1683097129000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01699468"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,12]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1985,12]]}},"alternative-id":["BF01699468"],"URL":"https:\/\/doi.org\/10.1007\/bf01699468","relation":{},"ISSN":["0025-5661","1433-0490"],"issn-type":[{"value":"0025-5661","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,12]]}}}