| Title:
|
Real-time and complexity problems in automata theory (English) |
| Title:
|
Problémy reálného času a složitosti v teorii automatů (Czech) |
| Author:
|
Bečvář, Jiří |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
1 |
| Issue:
|
6 |
| Year:
|
1965 |
| Pages:
|
(475)-498 |
| Summary lang:
|
Czech |
| . |
| Category:
|
math |
| . |
| MSC:
|
68Q17 |
| MSC:
|
68Q25 |
| idZBL:
|
Zbl 0192.08701 |
| . |
| Date available:
|
2009-09-24T15:37:30Z |
| Last updated:
|
2012-06-04 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/125286 |
| . |
| Reference:
|
[1] A. Grzegorczyk: "Some classes of recursive functions".Rozprawy matematyczne, IV (1953), Warsaw. Zbl 0052.24902, MR 0060426 |
| Reference:
|
[2] M. O. Rabin D. Scott: "Finite automata and their decision problems".IBM J. Research and Development, 3, (1959) 114-125. MR 0103795 |
| Reference:
|
[3] J. Myhill: "Linear bounded automata".WADD Tech. Note No. 60-165, Univ. of Pennsylvania Rept. No. 60-62 (1960). |
| Reference:
|
[4] N. Chomsky: "Three models for the description of language".IRE Trans. on Information Theory, IT-2, (1956) 113-124. Zbl 0156.25401 |
| Reference:
|
[5] S. C. Kleene E. L. Post: "The upper semi-lattice of degrees of recursive unsolvability".Ann. Math., 59, (1954) 379-407. MR 0061078 |
| Reference:
|
[6] M. O. Rabin: "Speed of computation of functions and classification of recursive sets".Bull. Res. Counc. of Israel, vol. 8F, (1959) 69-70. |
| Reference:
|
[7] H. Yamada: "Counting by a class of growing automata".PhD Thesis, Moore School of Elect. Eng., University of Pennsylvania (1960). |
| Reference:
|
[7a] H. Yamada: "Real time computation and recursive functions not real-time computable".IRE Trans. on Electronic Computers, EC-11 (1962) 753-760. MR 0152161 |
| Reference:
|
[8]
: .Oral communication by S. V. Jablonskij (1962). Zbl 1005.68507 |
| Reference:
|
[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. Zbl 0133.09801, MR 0136487 |
| Reference:
|
[10] J. Hartmanis R. E. Stearns: "On the computational complexity of algorithms".Trans. Amer. Math. Soc. (in press). MR 0170805 |
| Reference:
|
[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. |
| Reference:
|
[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. |
| Reference:
|
[13] M. O. Rabin: "Real time computation".Israel J. of Math., 1 (1963), 203-211. Zbl 0156.25603, MR 0163849 |
| Reference:
|
[14] B. A. Trachtenbrot: "Turing computations with logarithmic delay".(in Russian). Algebra i logika 3 (1964), no 4, 33-48. MR 0183645 |
| Reference:
|
[15] R. W. Ritchie: "Classes of predictably computable functions".Trans. Am. Math. Soc., 106 (1963) 139-173. Zbl 0107.01001, MR 0158822 |
| Reference:
|
[16] J. P. Cleave: "A hierarchy of primitive recursive functions".Zeitschrift f. math. Logik und Grundlagen d. Math. 9 (1963) 331-345. Zbl 0124.00303, MR 0159754 |
| Reference:
|
[17] M. Blum: "A machine-independent theory of complexity of recursive functions".PҺD Thesis, M.I.T., Departm. of Math. (1964). |
| Reference:
|
[18] S. N. Cole: "Real time computation by iterative arrays of finite state machines".PҺD Thesis, Computation Laboratory, Harvard University. Zbl 0172.20804 |
| Reference:
|
[19] A. G. Vituškin: "Ocenka složnosti zadači tabulirovanija".Gosudarstvennoe izdateľstvo fiziko-matematičeskoj literatury, Moscow 1959. |
| Reference:
|
[20] V. A. Uspenskij: „Lekcii o vyčislimych funkcijach".p. 470. Gosudarstvennoe izdateľstvo fiziko-matematičeskoj literatury, Moscow 1960. |
| Reference:
|
[21] F. C. Hennie: „Iterative arrays of logical circuits".M. I. T. Press 1961. |
| Reference:
|
[22] J. Holland: "Iterative circuit computers".Proc. Western Joint Computer Conf., pp. 259 - 265, San Francisco 1960. |
| Reference:
|
[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. |
| Reference:
|
[24] N. Chomsky: "Context-free grammars and push-down storage".Quaгterly Progress Report No. 65, M.I.T., 187-194 (1962). |
| Reference:
|
[25]
: .Oral communication. |
| Reference:
|
[26] B. A. Trachtenbrot: "Tabular representation of recursive operators".(in Russian). Doklady Akad. nauk SSSR, 101 (1955), 417-420. MR 0081860 |
| Reference:
|
[27] F. C. Hennie: "One-tape, off-line Turing machine computations".Information and Control (to be published). Reference from [12]. Zbl 0231.02048, MR 0191769 |
| Reference:
|
[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. |
| . |
