Time-restricted sequence generation. (English) Zbl 0191.18301

Full Text: DOI


[1] Cobham, A., Functional equations for register machines, (Proc. Hawaii International Conference on System Sciences (1968)), 10-13
[2] Fischer, P. C., Turing machines with a schedule to keep, Information and Control, 11, 138-146 (1967) · Zbl 0153.31701
[3] Fischer, P. C.; Meyer, A. R.; Rosenberg, A. L., Real-time counter machines, Proc. Eighth Ann. Symp. on Switching and Automata Theory, 148-154 (1967)
[4] Fischer, P. C.; Meyer, A. R.; Rosenberg, A. L., Counter machines and counter languages, Math. Systems Theory, 2, 265-283 (1968) · Zbl 0165.32002
[5] Hartmanis, J.; Stearns, R. E., On the computational complexity of algorithms, Trans. Amer. Math. Soc., 117, 285-306 (1965) · Zbl 0131.15404
[6] Hennie, F.; Stearns, R. E., Two-tape simulation of multitape turing machines, J. Assoc. Comput. Mach., 13, 533-546 (1966) · Zbl 0148.24801
[7] Meyer, A. R.; Rosenberg, A. L.; Fischer, P. C., Turing machines with several read-write heads, (Proc. Eighth Ann. Symp. on Switching and Automata Theory (1967)), 117-127
[8] Minsky, M. L., Recursive unsolvability of Post’s problem of tag and other topics in the theory of turing machines, Ann. of Math., 74, 437-455 (1961) · Zbl 0105.00802
[9] Rabin, M. O., Real-time computation, Israel J. Math., 1, 203-211 (1963) · Zbl 0156.25603
[10] Rosenberg, A. L., Real-time definable languages, J. Assoc. Comput. Mach., 645-662 (1967) · Zbl 0153.00902
[11] Thue, A., Über die Gegenseitige Lage Gleicher Teile Gewisser Zeichenreihen, Mat. Nat. Klasse 1, Kristiana (1913) · JFM 44.0462.01
[12] Yamada, H., Real-time computation and recursive functions not real-time computable, IRE Trans. E. C., 11, 753-760 (1962) · Zbl 0124.25006
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.