×

Real-time and complexity problems in automata theory. (English) Zbl 0192.08701


PDFBibTeX XMLCite
Full Text: EuDML

References:

[1] A. Grzegorczyk: ”Some classes of recursive functions”. Rozprawy matematyczne, IV (1953), Warsaw. · Zbl 0052.24902
[2] M. O. Rabin D. Scott: ”Finite automata and their decision problems”. IBM J. Research and Development, 3, (1959) 114-125. · Zbl 0158.25404
[3] J. Myhill: ”Linear bounded automata”. WADD Tech. Note No. 60-165, Univ. of Pennsylvania Rept. No. 60-62 (1960).
[4] N. Chomsky: ”Three models for the description of language”. IRE Trans. on Information Theory, IT-2, (1956) 113-124. · Zbl 0156.25401 · doi:10.1109/TIT.1956.1056813
[5] S. C. Kleene E. L. Post: ”The upper semi-lattice of degrees of recursive unsolvability”. Ann. Math., 59, (1954) 379-407. · Zbl 0057.24703 · doi:10.2307/1969708
[6] M. O. Rabin: ”Speed of computation of functions and classification of recursive sets”. Bull. Res. Counc. of Israel, vol. 8F, (1959) 69-70.
[7] H. Yamada: ”Counting by a class of growing automata”. PhD Thesis, Moore School of Elect. Eng., University of Pennsylvania (1960).
[8] H. Yamada: ”Real time computation and recursive functions not real-time computable”. IRE Trans. on Electronic Computers, EC-11 (1962) 753-760. · Zbl 0124.25006
[9] Oral communication by S. V. Jablonskij (1962). · Zbl 1005.68507 · doi:10.1287/mnsc.8.3.344
[10] R. McNaughton: ”The theory of automata, a survey”. Advances in Computers, vol. 2, 379-421 F.L. Alt, Academic Press, New York 1961. · Zbl 0133.09801 · doi:10.1016/S0065-2458(08)60144-8
[11] J. Hartmanis R. E. Stearns: ”On the computational complexity of algorithms”. Trans. Amer. Math. Soc. · Zbl 0156.25604
[12] J. Hartmanis R. E. Stearns: ”Computational complexity of recursive sequences”. Proc. of the Fifth Annual Symposium on Switching Circuit Theory and Logical Design, held at Princeton University, (1964) 82-90.
[13] J. Hartmanis P. M. Lewis II R. E. Stearns: ”Classification of computations by time and memory requirements”. Text of an invited paper read at the IFIP 65 Congress in New York, May 1965. · Zbl 0203.16401
[14] M. O. Rabin: ”Real time computation”. Israel J. of Math., 1 (1963), 203-211. · Zbl 0156.25603 · doi:10.1007/BF02759719
[15] B. A. Trachtenbrot: ”Turing computations with logarithmic delay”. (in Russian). Algebra i logika 3 (1964), no 4, 33-48.
[16] R. W. Ritchie: ”Classes of predictably computable functions”. Trans. Am. Math. Soc., 106 (1963) 139-173. · Zbl 0107.01001 · doi:10.2307/1993719
[17] J. P. Cleave: ”A hierarchy of primitive recursive functions”. Zeitschrift f. math. Logik und Grundlagen d. Math. 9 (1963) 331-345. · Zbl 0124.00303 · doi:10.1002/malq.19630092202
[18] M. Blum: ”A machine-independent theory of complexity of recursive functions”. P\?D Thesis, M.I.T., Departm. of Math. (1964). · Zbl 0155.01503
[19] S. N. Cole: ”Real time computation by iterative arrays of finite state machines”. P\?D Thesis, Computation Laboratory, Harvard University. · Zbl 0172.20804 · doi:10.1109/T-C.1969.222663
[20] A. G. Vituškin: ”Ocenka složnosti zadači tabulirovanija”. Gosudarstvennoe izdateľstvo fiziko-matematičeskoj literatury, Moscow 1959.
[21] V. A. Uspenskij: ”Lekcii o vyčislimych funkcijach”. p. 470. Gosudarstvennoe izdateľstvo fiziko-matematičeskoj literatury, Moscow 1960.
[22] F. C. Hennie: ”Iterative arrays of logical circuits”. M. I. T. Press 1961.
[23] J. Holland: ”Iterative circuit computers”. Proc. Western Joint Computer Conf., pp. 259 - 265, San Francisco 1960.
[24] J. Bečvář: ”Finite and combinatorial automata. Turing automata with a programming tape”. Proc. of the IFIP congress 62, 391-394, North-Holland Publ. Co., Amsterdam 1963.
[25] N. Chomsky: ”Context-free grammars and push-down storage”. Quarterly Progress Report No. 65, M.I.T., 187-194 (1962).
[26] Oral communication. · Zbl 0331.01002 · doi:10.1016/0315-0860(75)90104-4
[27] B. A. Trachtenbrot: ”Tabular representation of recursive operators”. (in Russian). Doklady Akad. nauk SSSR, 101 (1955), 417-420.
[28] F. C. Hennie: ”One-tape, off-line Turing machine computations”. Information and Control (to be published). Reference from [12]. · Zbl 0231.02048 · doi:10.1016/S0019-9958(65)90399-2
[29] A. V. Gladkij: ”On the complexity of derivations in immediate constituents grammars”. (In Russian). Algebra i logika 3 (1964), no 5 - 6, 29 - 44.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.