Real-time and complexity problems in automata theory

Bečvář, Jiří

Kybernetika, Tome 1 (1965) no. 6, pp. 475-498

Détail

Classification : 68Q17, 68Q25

Bibliographie

[1] A. Grzegorczyk: "Some classes of recursive functions". Rozprawy matematyczne, IV (1953), Warsaw. | MR | Zbl

[2] M. O. Rabin D. Scott: "Finite automata and their decision problems". IBM J. Research and Development, 3, (1959) 114-125. | MR

[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

[5] S. C. Kleene E. L. Post: "The upper semi-lattice of degrees of recursive unsolvability". Ann. Math., 59, (1954) 379-407. | MR

[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).

[7a] H. Yamada: "Real time computation and recursive functions not real-time computable". IRE Trans. on Electronic Computers, EC-11 (1962) 753-760. | MR

[8] Oral communication by S. V. Jablonskij (1962). | Zbl

[9] R. McNaughton: "The theory of automata, a survey". Advances in Computers, vol. 2, 379-421, ed. F.L. Alt, Academic Press, New York 1961. | MR | Zbl

[10] J. Hartmanis R. E. Stearns: "On the computational complexity of algorithms". Trans. Amer. Math. Soc. (in press). | MR

[11] 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.

[12] 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.

[13] M. O. Rabin: "Real time computation". Israel J. of Math., 1 (1963), 203-211. | MR | Zbl

[14] B. A. Trachtenbrot: "Turing computations with logarithmic delay". (in Russian). Algebra i logika 3 (1964), no 4, 33-48. | MR

[15] R. W. Ritchie: "Classes of predictably computable functions". Trans. Am. Math. Soc., 106 (1963) 139-173. | MR | Zbl

[16] J. P. Cleave: "A hierarchy of primitive recursive functions". Zeitschrift f. math. Logik und Grundlagen d. Math. 9 (1963) 331-345. | MR | Zbl

[17] M. Blum: "A machine-independent theory of complexity of recursive functions". PҺD Thesis, M.I.T., Departm. of Math. (1964).

[18] S. N. Cole: "Real time computation by iterative arrays of finite state machines". PҺD Thesis, Computation Laboratory, Harvard University. | Zbl

[19] A. G. Vituškin: "Ocenka složnosti zadači tabulirovanija". Gosudarstvennoe izdateľstvo fiziko-matematičeskoj literatury, Moscow 1959.

[20] V. A. Uspenskij: „Lekcii o vyčislimych funkcijach". p. 470. Gosudarstvennoe izdateľstvo fiziko-matematičeskoj literatury, Moscow 1960.

[21] F. C. Hennie: „Iterative arrays of logical circuits". M. I. T. Press 1961.

[22] J. Holland: "Iterative circuit computers". Proc. Western Joint Computer Conf., pp. 259 - 265, San Francisco 1960.

[23] 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.

[24] N. Chomsky: "Context-free grammars and push-down storage". Quaгterly Progress Report No. 65, M.I.T., 187-194 (1962).

[25] Oral communication.

[26] B. A. Trachtenbrot: "Tabular representation of recursive operators". (in Russian). Doklady Akad. nauk SSSR, 101 (1955), 417-420. | MR

[27] F. C. Hennie: "One-tape, off-line Turing machine computations". Information and Control (to be published). Reference from [12]. | MR | Zbl

[28] A. V. Gladkij: "On the complexity of derivations in immediate constituents grammars". (In Russian). Algebra i logika 3 (1964), no 5 - 6, 29 - 44.