×

zbMATH — the first resource for mathematics

Counter machines and counter languages. (English) Zbl 0165.32002

PDF BibTeX XML Cite
Full Text: DOI
References:
[1] A. Cobham, Time and memory capacity bounds for machines which recognize squares or palindromes,IBM Research Report RC-1621, 1966.
[2] P. C. Fischer, Turing machines with restricted memory access.Information and Control 9 (1966), 364–379. · Zbl 0145.24205 · doi:10.1016/S0019-9958(66)80003-7
[3] M. J. Fischer andA. L. Rosenberg, Real-time solutions of the origin-crossing problem.Math. Systems Theory 2 (1968), 257–263. · Zbl 0181.01601 · doi:10.1007/BF01694010
[4] S. Ginsburg,The Mathematical Theory of Context-Free Languages, McGraw-Hill, New York, 1966. · Zbl 0184.28401
[5] S. Ginsburg andE. H. Spanier, BoundedAlgol-like languages,Trans. Amer. Math. Soc. 113 (1964), 333–368. · Zbl 0142.24803
[6] J. Hartmanis andR. E. Stearns, On the computational complexity of algorithms,Trans. Amer. Math. Soc. 117 (1965), 285–306. · Zbl 0131.15404 · doi:10.1090/S0002-9947-1965-0170805-7
[7] R. Laing, Realization and complexity of commutative events,Univ. of Mich. Technical Report 03105-48-T, 1967.
[8] M. Minsky, Recursive unsolvability of Post’s problem of tag and other topics in the theory of Turing machines,Ann. of Math. 74 (1961), 437–455. · Zbl 0105.00802 · doi:10.2307/1970290
[9] A. G. Oettinger, Automatic syntactic analysis and the pushdown store,Proc. 12th Ann. Sympos. in Appl. Math., 1960, pp. 104–129.
[10] R. J. Parikh, On context-free languages.J. Assoc. Comput. Mach. 13 (1966), 570–581. · Zbl 0154.25801
[11] M. O. Rabin, Real-time computation,Israel J. Math. 1 (1963), 203–211. · Zbl 0156.25603 · doi:10.1007/BF02759719
[12] M. O. Rabin andD. Scott, Finite automata and their decision problems,IBM J. Res. Develop. 3 (1959), 114–125. · doi:10.1147/rd.32.0114
[13] A. L. Rosenberg, Real-time definable languages,J. Assoc. Comput. Mach. 14 (1967), 645–662. · Zbl 0153.00902
[14] R. E. Stearns, J. Hartmanis andP. Lewis, Hierarchies of memory-limited computation,Proc. 6th Ann. Sympos. Switching Circuit Theory and Logical Design, Ann Arbor, Mich., 1966, pp. 179–190.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.