{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T18:07:08Z","timestamp":1649009228662},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1976,12,1]],"date-time":"1976-12-01T00:00:00Z","timestamp":218246400000},"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":[[1976,12]]},"DOI":"10.1007\/bf01683261","type":"journal-article","created":{"date-parts":[[2005,5,13]],"date-time":"2005-05-13T23:29:17Z","timestamp":1116026957000},"page":"33-52","source":"Crossref","is-referenced-by-count":9,"title":["On the complexity of finite, pushdown, and stack automata"],"prefix":"10.1007","volume":"10","author":[{"suffix":"III","given":"H. B.","family":"Hunt","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"BF01683261_CR1","doi-asserted-by":"crossref","unstructured":"S. A. Cook, The complexity of theorem-proving procedures.Proc. 3rd Annual ACM Symp. on Theory of Computing, May, 1971.","DOI":"10.1145\/800157.805047"},{"key":"BF01683261_CR2","volume-title":"Complexity of Computer Computations","author":"R. M. Karp","year":"1972","unstructured":"R. M. Karp, Reducibility among combinatorial problems, inComplexity of Computer Computations, (R. E. Miller and J. W. Thatcher, eds.), Plenum Press, New York, 1972."},{"key":"BF01683261_CR3","unstructured":"A. R. Meyer, Weak monadic second order of successor is not elementary recursive-preliminary report (unpublished)."},{"key":"BF01683261_CR4","volume-title":"SIAM-AMS Proc., vol. 7","author":"M. J. Fischer","year":"1974","unstructured":"M. J. Fischer andM. O. Rabin, Super-exponential complexity of Presburger arithmetic,SIAM-AMS Proc., vol. 7, Amer. Math. Soc., Providence, R.I., 1974."},{"key":"BF01683261_CR5","doi-asserted-by":"crossref","unstructured":"L. J. Stockmeyer andA. R. Meyer, World problems requiring exponential time: preliminary report,Proc. 5th Annual ACM Symp. on Theory of Computing, May, 1973.","DOI":"10.1145\/800125.804029"},{"key":"BF01683261_CR6","doi-asserted-by":"crossref","unstructured":"H. B. Hunt, III andD. J. Rosenkrantz, Computational parallels between the regular and context-free languages,Proc. 6th Annual ACM Symposium on Theory of Computing, May, 1974.","DOI":"10.1145\/800119.803885"},{"key":"BF01683261_CR7","unstructured":"H. B. Hunt, III,D. J. Rosenkrantz, andT. G. Szymanski, On the equivalence, containment, and covering problems for the regular and context-free languages (submitted for publication)."},{"key":"BF01683261_CR8","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W. J. Savitch","year":"1970","unstructured":"W. J. Savitch, Relationships between nondeterministic and deterministic tape complexities,J. Comput. System Sci. 4 (1970), 177\u2013192.","journal-title":"J. Comput. System Sci."},{"key":"BF01683261_CR9","volume-title":"SIAM-AMS Proc., vol. 7","author":"J. Hartmanis","year":"1974","unstructured":"J. Hartmanis andH. B. Hunt, III, The lba problem and its importance in the theory of computing,SIAM-AMS Proc., vol. 7, Amer. Math. Soc. Providence, R.I., 1974."},{"key":"BF01683261_CR10","unstructured":"N. Jones, Preliminary report: reducibility among combinatorial problems in logn space.Proc. 7th Annual Princeton Conference on Information Sciences and Systems, March, 1973."},{"key":"BF01683261_CR11","doi-asserted-by":"crossref","unstructured":"I. H. Sudborough, On tape-bounded complexity classes and multi-head finite automata,Proc. 14th Annual IEEE Symp. on Switching and Automata Theory, October, 1973.","DOI":"10.1109\/SWAT.1973.20"},{"key":"BF01683261_CR12","doi-asserted-by":"crossref","unstructured":"N. D. Jones andW. T. Laaser, Complete problems for deterministic polynomial time,Proc. 6th Annual ACM Symp. on Theory of Computing, May, 1974.","DOI":"10.1145\/800119.803883"},{"key":"BF01683261_CR13","doi-asserted-by":"crossref","unstructured":"S. A. Cook, An observation on time-storage tradeoff,Proc. 5th Annual ACM Symp. on Theory of Computing, May, 1973.","DOI":"10.1145\/800125.804032"},{"key":"BF01683261_CR14","doi-asserted-by":"crossref","unstructured":"S. A. Cook andR. Sethi, Storage requirements for deterministic polynomial time recognizable languages,Proc. 6th Annual ACM Symp. on Theory of Computing, May, 1974.","DOI":"10.1145\/800119.803882"},{"key":"BF01683261_CR15","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1145\/321526.321529","volume":"16","author":"A. V. Aho","year":"1969","unstructured":"A. V. Aho, Nested stack automata,J. Assoc. Comput. Mach. 16 (1969), 383\u2013406.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01683261_CR16","volume-title":"Formal Languages and Their Relation to Automata","author":"J. E. Hopcroft","year":"1969","unstructured":"J. E. Hopcroft andJ. D. Ullman,Formal Languages and Their Relation to Automata, Addison-Wesley, Reading, Mass., 1969."},{"key":"BF01683261_CR17","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1145\/321479.321488","volume":"15","author":"A. V. Aho","year":"1968","unstructured":"A. V. Aho, Indexed grammars\u2014an extension of context-free grammars,J. Assoc. Comput. Mach. 15 (1968), 647\u2013671.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01683261_CR18","doi-asserted-by":"crossref","unstructured":"M. J. Fischer, \u201cGrammars with Macro-like Productions,\u201d Ph.D. Dissertation, Harvard University, 1968.","DOI":"10.1109\/SWAT.1968.12"},{"key":"BF01683261_CR19","doi-asserted-by":"crossref","unstructured":"M. J. Fischer, Grammars with macro-like productions,Proc. 9th Annual IEEE Symp. on Switching and Automata Theory, October, 1968.","DOI":"10.1109\/SWAT.1968.12"},{"key":"BF01683261_CR20","volume-title":"Theory of Recursive Functions and Effective Computability","author":"H. Rogers Jr.","year":"1967","unstructured":"H. Rogers, Jr.,Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York, 1967."},{"key":"BF01683261_CR21","doi-asserted-by":"crossref","unstructured":"W. C. Rounds, Complexity of recognition in intermediate-level languages,Proc. 14th Annual IEEE Symp. on Switching and Automata Theory, October, 1973.","DOI":"10.1109\/SWAT.1973.5"},{"key":"BF01683261_CR22","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/S0022-0000(67)80013-8","volume":"1","author":"J. E. Hopcroft","year":"1967","unstructured":"J. E. Hopcroft andJ. D. Ullman, Nonerasing stack automata,J. Comput. System Sci. 1 (1967), 166\u2013186.","journal-title":"J. Comput. System Sci."},{"key":"BF01683261_CR23","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/321623.321625","volume":"18","author":"S. A. Cook","year":"1971","unstructured":"S. A. Cook, Characterizations of pushdown machines in terms of time-bounded computers,J. Assoc. Comput. Mach. 18 (1971), 4\u201318.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01683261_CR24","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/S0022-0000(71)80029-6","volume":"5","author":"O. H. Ibarra","year":"1971","unstructured":"O. H. Ibarra, Characterizations of some tape and time complexity classes of Turing machines in terms of multi-head and auxiliary stack automata,J. Comput. System Sci. 5 (1971), 88\u2013117.","journal-title":"J. Comput. System Sci."},{"key":"BF01683261_CR25","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1145\/321356.321362","volume":"13","author":"F. C. Hennie","year":"1966","unstructured":"F. C. Hennie andR. E. Stearns, Two-tape simulation of multi-tape Turing macnines,J. Assoc. Comput. Mach,13 (1966), 533\u2013546.","journal-title":"J. Assoc. Comput. Mach"},{"key":"BF01683261_CR26","doi-asserted-by":"crossref","first-page":"608","DOI":"10.1145\/321724.321727","volume":"19","author":"O. H. Ibarra","year":"1972","unstructured":"O. H. Ibarra, A note concerning nondeterministic tape complexities.J. Assoc. Comput. Mach. 19 (1972), 608\u2013612.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01683261_CR27","doi-asserted-by":"crossref","unstructured":"J. I. Seiferas, M. J. Fischer, andA. R. Meyer, Refinements of the nondeterministic time and space hierarchies,Proc. 14th Annual IEEE Symp. on Switching and Automata Theory, October, 1973.","DOI":"10.1109\/SWAT.1973.25"},{"key":"BF01683261_CR28","doi-asserted-by":"crossref","unstructured":"W. C. Rounds, Tree-oriented proofs of some theorems on context-free and indexed languages,Proc. 2nd Annual ACM Symp. on Theory of Computing, May, 1970.","DOI":"10.1145\/800161.805156"},{"key":"BF01683261_CR29","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/BF01695769","volume":"4","author":"W. C. Rounds","year":"1970","unstructured":"W. C. Rounds, Mappings and grammars on trees,Math. Systems Theory 4 (1970), 257\u2013287.","journal-title":"Math. Systems Theory"},{"key":"BF01683261_CR30","doi-asserted-by":"crossref","unstructured":"V. Rajlich, Absolutely parallel grammars and two-way deterministic finite-state transducers,Proc. 3rd Annual ACM Symp. on Theory of Computing, May 1971.","DOI":"10.1145\/800157.805045"},{"key":"BF01683261_CR31","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1137\/0202025","volume":"2","author":"S. A. Greibach","year":"1973","unstructured":"S. A. Greibach, The hardest context-free language,SIAM J. Comput. 2 (1973), 304\u2013310.","journal-title":"SIAM J. Comput."},{"key":"BF01683261_CR32","doi-asserted-by":"crossref","unstructured":"H. B. Hunt, III, On the time and tape complexity of languages I,Proc. 5th Annual ACM Symp. on Theory of Computing, May, 1973.","DOI":"10.1145\/800125.804030"},{"key":"BF01683261_CR33","doi-asserted-by":"crossref","unstructured":"H. B. Hunt, III, \u201cOn the Time and Tape Complexity of Languages,\u201d Ph.D. Dissertation, Cornell University, 1973.","DOI":"10.1145\/800125.804030"},{"key":"BF01683261_CR34","doi-asserted-by":"crossref","unstructured":"R. Book, On languages accepted in polynomial time,SIAM J. Comput. 1 (1972).","DOI":"10.1137\/0201019"},{"key":"BF01683261_CR35","doi-asserted-by":"crossref","unstructured":"Z. Galil, Two-way deterministic pushdown automaton languages and some open problems in the theory of computation,Proc. 15th Annual IEEE Symp. on Switching and Automata Theory, October, 1974.","DOI":"10.1109\/SWAT.1974.29"},{"key":"BF01683261_CR36","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1145\/321495.321504","volume":"16","author":"D. J. Rosenkrantz","year":"1969","unstructured":"D. J. Rosenkrantz, Programmed grammars and classes of formal languages,J. Assoc. Comput. Mach. 16 (1969), 107\u2013131.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01683261_CR37","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/S0022-0000(69)80015-2","volume":"3","author":"S. A. Greibach","year":"1969","unstructured":"S. A. Greibach andJ. E. Hopcroft, Scattered context grammars,J. Comput. System Sci. 3 (1969), 233\u2013247.","journal-title":"J. Comput. System Sci."},{"key":"BF01683261_CR38","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1016\/S0019-9958(68)91087-5","volume":"13","author":"A. V. Aho","year":"1968","unstructured":"A. V. Aho, J. E. Hopcroft, andJ. D. Ullman, Time and tape complexity of pushdown automaton languages,Information and Control 13 (1968), 186\u2013206.","journal-title":"Information and Control"},{"key":"BF01683261_CR39","unstructured":"H. B. Hunt, III, \u201cOn the Complexity of Finite, Pushdown, and Stack Automata,\u201d MRC Technical Summary Report No. 1504, Mathematics Research Center, University of Wisconsin-Madison, 1975."}],"container-title":["Mathematical Systems Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01683261.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01683261\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01683261","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T09:51:38Z","timestamp":1586253098000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01683261"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1976,12]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1976,12]]}},"alternative-id":["BF01683261"],"URL":"https:\/\/doi.org\/10.1007\/bf01683261","relation":{},"ISSN":["0025-5661","1433-0490"],"issn-type":[{"value":"0025-5661","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[1976,12]]}}}