{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,22]],"date-time":"2024-08-22T05:14:51Z","timestamp":1724303691814},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1978,12,1]],"date-time":"1978-12-01T00:00:00Z","timestamp":281318400000},"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":[[1978,12]]},"DOI":"10.1007\/bf01776575","type":"journal-article","created":{"date-parts":[[2005,6,18]],"date-time":"2005-06-18T06:29:16Z","timestamp":1119076156000},"page":"219-231","source":"Crossref","is-referenced-by-count":21,"title":["Real-time computations with restricted nondeterminism"],"prefix":"10.1007","volume":"12","author":[{"given":"Patrick C.","family":"Fischer","sequence":"first","affiliation":[]},{"given":"Chandra M. R.","family":"Kintala","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF01776575_CR1","first-page":"75","volume":"VII","author":"S. O. Aanderaa","year":"1974","unstructured":"S. O. Aanderaa, Onk-tape versus (k-1)-tape Real Time Computation, inComplexity of Computation, SIAM-AMS Proceedings, Vol. VII, 75\u201396 (1974).","journal-title":"Complexity of Computation, SIAM-AMS Proceedings"},{"key":"BF01776575_CR2","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/BF01705890","volume":"4","author":"R. V. Book","year":"1970","unstructured":"R. V. Book, and S. A. Greibach, Quasi-Realtime Languages,Math. Systems Theory, 4, 97\u2013111 (1970).","journal-title":"Math. Systems Theory"},{"key":"BF01776575_CR3","doi-asserted-by":"crossref","unstructured":"S. A. Cook, The Complexity of Theorem Proving Procedures,Proc. of 3rd Annual ACM Symposium on Theory of Computing, 151\u2013158 (1971).","DOI":"10.1145\/800157.805047"},{"key":"BF01776575_CR4","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1016\/S0019-9958(66)80003-7","volume":"9","author":"P. C. Fischer","year":"1966","unstructured":"P. C. Fischer, Turing Machines with Restricted Memory Access,Inform. Control, 9, 364\u2013379 (1966).","journal-title":"Inform. Control"},{"key":"BF01776575_CR5","doi-asserted-by":"crossref","first-page":"590","DOI":"10.1145\/321724.321726","volume":"19","author":"P. C. Fischer","year":"1972","unstructured":"P. C. Fischer, A. R. Meyer, and A. L. Rosenberg, Real-Time Simulation of Multihead Tape Units,J. Assoc. Comp. Mach., 19, 590\u2013607 (1972).","journal-title":"J. Assoc. Comp. Mach."},{"key":"BF01776575_CR6","first-page":"1","volume":"87","author":"S. Ginsburg","year":"1969","unstructured":"S. Ginsburg, and S. A. Greibach, Abstract Families of Languages,Memoirs of American Math. Society, No. 87, 1\u201332 (1969).","journal-title":"Memoirs of American Math. Society"},{"key":"BF01776575_CR7","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1090\/S0002-9947-1965-0170805-7","volume":"117","author":"J. Hartmanis","year":"1965","unstructured":"J. Hartmanis, and R. E. Stearns, On the Computational Complexity of Algorithms,Trans. Amer. Math. Soc., 117, 285\u2013306 (1965).","journal-title":"Trans. Amer. Math. Soc."},{"key":"BF01776575_CR8","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R. M. Karp","year":"1972","unstructured":"R. M. Karp, Reducibilities among Combinatorial Problems,Complexity of Computer Computations, Plenum Press, New York, 85\u2013104 (1972)."},{"key":"BF01776575_CR9","doi-asserted-by":"crossref","unstructured":"C. M. R. Kintala, Computations with a Restricted Number of Nondeterministic Steps, Doctoral Thesis, The Pennsylvania State University, 1977.","DOI":"10.1145\/800105.803407"},{"key":"BF01776575_CR10","doi-asserted-by":"crossref","unstructured":"C. M. R. Kintala, and P. C. Fischer, Computations with a Restricted Number of Nondeterministic Steps (Extended Abstract),Proc. 9th Annual Symposium on Theory of Computing, 178\u2013185 (1977).","DOI":"10.1145\/800105.803407"},{"key":"BF01776575_CR11","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/S0019-9958(64)90120-2","volume":"7","author":"S. Y. Kuroda","year":"1964","unstructured":"S. Y. Kuroda, Classes of Languages and Linear-Bounded Automata,Inform. Control, 7, 207\u2013223 (1964).","journal-title":"Inform. Control"},{"key":"BF01776575_CR12","doi-asserted-by":"crossref","unstructured":"B. L. Leong, and J. Seiferas, New Real-time Simulations of Multi-head Tape Units,Proc. 9th Annual Symp. on Theory of Computing, 239\u2013248 (1977).","DOI":"10.1145\/800105.803414"},{"key":"BF01776575_CR13","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1147\/rd.32.0114","volume":"3","author":"M. O. Rabin","year":"1959","unstructured":"M. O. Rabin, and D. Scott, Finite Automata and their Decision Problems,IBM J. of Research and Development, 3, 114\u2013125 (1959).","journal-title":"IBM J. of Research and Development"},{"key":"BF01776575_CR14","doi-asserted-by":"crossref","first-page":"645","DOI":"10.1145\/321420.321423","volume":"14","author":"A. L. Rosenberg","year":"1967","unstructured":"A. L. Rosenberg, Real-time Definable Languages,J. Assoc. Comp. Mach., 14, 645\u2013662 (1967).","journal-title":"J. Assoc. Comp. Mach."},{"key":"BF01776575_CR15","doi-asserted-by":"crossref","unstructured":"H. Yamada, Real-time Computation and Recursive Functions not Real-time Computable,IRE Trans. on Electronic Computers, EC-11, 753\u2013760 (1962).","DOI":"10.1109\/TEC.1962.5219459"}],"container-title":["Mathematical Systems Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01776575.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01776575\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01776575","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T20:45:42Z","timestamp":1586292342000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01776575"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1978,12]]},"references-count":15,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1978,12]]}},"alternative-id":["BF01776575"],"URL":"https:\/\/doi.org\/10.1007\/bf01776575","relation":{},"ISSN":["0025-5661","1433-0490"],"issn-type":[{"value":"0025-5661","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[1978,12]]}}}