Real-time and complexity problems in automata theory

Jiří Bečvář

Kybernetika (1965)

  • Volume: 01, Issue: 6, page (475)-498
  • ISSN: 0023-5954

How to cite

top

Bečvář, Jiří. "Real-time and complexity problems in automata theory." Kybernetika 01.6 (1965): (475)-498. <http://eudml.org/doc/28441>.

@article{Bečvář1965,
author = {Bečvář, Jiří},
journal = {Kybernetika},
keywords = {languages, automata, networks},
language = {eng},
number = {6},
pages = {(475)-498},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Real-time and complexity problems in automata theory},
url = {http://eudml.org/doc/28441},
volume = {01},
year = {1965},
}

TY - JOUR
AU - Bečvář, Jiří
TI - Real-time and complexity problems in automata theory
JO - Kybernetika
PY - 1965
PB - Institute of Information Theory and Automation AS CR
VL - 01
IS - 6
SP - (475)
EP - 498
LA - eng
KW - languages, automata, networks
UR - http://eudml.org/doc/28441
ER -

References

top
  1. A. Grzegorczyk, "Some classes of recursive functions", Rozprawy matematyczne, IV (1953), Warsaw. (1953) Zbl0052.24902MR0060426
  2. M. O. Rabin D. Scott, "Finite automata and their decision problems", IBM J. Research and Development, 3, (1959) 114-125. (1959) MR0103795
  3. J. Myhill, "Linear bounded automata", WADD Tech. Note No. 60-165, Univ. of Pennsylvania Rept. No. 60-62 (1960). (1960) 
  4. N. Chomsky, "Three models for the description of language", IRE Trans. on Information Theory, IT-2, (1956) 113-124. (1956) Zbl0156.25401
  5. S. C. Kleene E. L. Post, "The upper semi-lattice of degrees of recursive unsolvability", Ann. Math., 59, (1954) 379-407. (1954) MR0061078
  6. M. O. Rabin, "Speed of computation of functions and classification of recursive sets", Bull. Res. Counc. of Israel, vol. 8F, (1959) 69-70. (1959) 
  7. H. Yamada, "Counting by a class of growing automata", PhD Thesis, Moore School of Elect. Eng., University of Pennsylvania (1960). (1960) 
  8. H. Yamada, "Real time computation and recursive functions not real-time computable", IRE Trans. on Electronic Computers, EC-11 (1962) 753-760. (1962) MR0152161
  9. [unknown], Oral communication by S. V. Jablonskij (1962). (1962) Zbl1005.68507
  10. R. McNaughton, "The theory of automata, a survey", Advances in Computers, vol. 2, 379-421, ed. F.L. Alt, Academic Press, New York 1961. (1961) Zbl0133.09801MR0136487
  11. J. Hartmanis R. E. Stearns, "On the computational complexity of algorithms", Trans. Amer. Math. Soc. (in press). MR0170805
  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. (1964) 
  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. (1965) 
  14. M. O. Rabin, "Real time computation", Israel J. of Math., 1 (1963), 203-211. (1963) Zbl0156.25603MR0163849
  15. B. A. Trachtenbrot, "Turing computations with logarithmic delay", (in Russian). Algebra i logika 3 (1964), no 4, 33-48. (1964) MR0183645
  16. R. W. Ritchie, "Classes of predictably computable functions", Trans. Am. Math. Soc., 106 (1963) 139-173. (1963) Zbl0107.01001MR0158822
  17. J. P. Cleave, "A hierarchy of primitive recursive functions", Zeitschrift f. math. Logik und Grundlagen d. Math. 9 (1963) 331-345. (1963) Zbl0124.00303MR0159754
  18. M. Blum, "A machine-independent theory of complexity of recursive functions", PҺD Thesis, M.I.T., Departm. of Math. (1964). (1964) 
  19. S. N. Cole, "Real time computation by iterative arrays of finite state machines", PҺD Thesis, Computation Laboratory, Harvard University. Zbl0172.20804
  20. A. G. Vituškin, "Ocenka složnosti zadači tabulirovanija", Gosudarstvennoe izdateľstvo fiziko-matematičeskoj literatury, Moscow 1959. (1959) 
  21. V. A. Uspenskij, „Lekcii o vyčislimych funkcijach", p. 470. Gosudarstvennoe izdateľstvo fiziko-matematičeskoj literatury, Moscow 1960. (1960) 
  22. F. C. Hennie, „Iterative arrays of logical circuits", M. I. T. Press 1961. (1961) 
  23. J. Holland, "Iterative circuit computers", Proc. Western Joint Computer Conf., pp. 259 - 265, San Francisco 1960. (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. (1963) 
  25. N. Chomsky, "Context-free grammars and push-down storage", Quaгterly Progress Report No. 65, M.I.T., 187-194 (1962). (194) 
  26. [unknown], Oral communication. 
  27. B. A. Trachtenbrot, "Tabular representation of recursive operators", (in Russian). Doklady Akad. nauk SSSR, 101 (1955), 417-420. (1955) MR0081860
  28. F. C. Hennie, "One-tape, off-line Turing machine computations", Information and Control (to be published). Reference from [12]. Zbl0231.02048MR0191769
  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. (1964) 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.