Abstract
Structural properties, local and asymptotic, of members of a class of simple, realtime generable sequences are analyzed.
Article PDF
Similar content being viewed by others
References
J. R. Büchi, Weak second-order arithmetic and finite automata,Z. Math. Logik Grundlagen Math. 6 (1960), 66–92.
R. Bumby andE. Ellentuck, Finitely additive measures and the first digit problem,Fund. Math. 65 (1969), 33–42.
A. Cobham, “On the Hartmanis-Stearns problem for a class of tag machines”, IEEE Conference Record of the 1968 Ninth Annual Symposium on Switching and Automata Theory, Schenectady (1968), 51–60.
A. Cobham, On the base-dependence of sets of numbers recognizable by finite automata,Math. Systems Theory 3 (1969), 186–192.
B. D. Craven, On digital distribution in some integer sequences,J. Austral. Math. Soc. 5 (1965), 325–330.
C. C. Elgot, Decision problems of finite automata design and related arithmetics,Trans. Amer. Math. Soc. 98 (1961), 21–51.
P. C. Fischer, A. R. Meyer andA. L. Rosenberg, Time-restricted sequence generation,J. Comput. System Sci. 4 (1970), 50–73.
B. J. Flehinger, On the probability that a random integer has initial digit A,Amer. Math. Monthly 73 (1966), 1056–1061.
F. R. Gantmacher,The Theory of Matrices (2 vols.), Chelsea, New York, 1960.
S. Ginsburg,The Mathematical Theory of Context-Free Languages, McGraw-Hill, New York, 1966.
W. H. Gottschalk andG. A. Hedlund,Topological Dynamics, Amer. Math. Soc., Providence, R.I., 1955.
H. Halberstam andK. F. Roth,Sequences, Vol. I, Oxford Univ. Press, Oxford, 1966.
G. H. Hardy andE. M. Wright,An Introduction to the Theory of Numbers, fourth edition, Oxford Univ. Press, Oxford, 1965.
J. Hartmanis andH. Shank, On the recognition of primes by automata,J. Assoc. Comput. Mach. 15 (1968), 328–389.
J. Hartmanis andR. E. Stearns, On the computational complexity of algorithms,Trans. Amer. Math. Soc. 117 (1965), 285–306.
G. A. Hedlund, Remarks on the work of Axel Thue on sequences,Nordisk Mat. Tidskr. 15 (1967), 148–150.
G. A. Hedlund, Endomorphisms and automorphisms of the shift dynamical system,Math. Systems Theory 3 (1969), 320–375.
L. Hellerman, W. L. Duda andS. Winograd, Continuity and realizability of sequence transformations,IEEE Trans. Electronic Computers EC-15 (1966), 560–569.
M. Keane, Generalized Morse sequences,Z. Wahrscheinlichkeitstheorie Verw. Gebiete 10 (1968), 335–353.
W. J. LeVeque,Topics in Number Theory (2 vols.), Addison-Wesley, Reading, Mass., 1956.
M. L. Minsky,Computation: Finite and Infinite Machines, Prentice-Hall, Englewood Cliffs, N.J., 1967.
M. Minsky andS. Papert, Unrecognizable sets of numbers,J. Assoc. Comput. Mach. 13 (1966), 281–286.
D. J. Newman, On the number of binary digits in a multiple of three,Proc. Amer. Math. Soc. 21 (1969), 719–721.
M. O. Rabin andD. Scott, Finite automata and their decision problems,IBM J. Res. Develop. 3 (1959), 114–125.
G. N. Raney, Sequential functions,J. Assoc. Comput. Mach. 5 (1958), 177–180.
R. W. Ritchie, Finite automata and the set of squares,J. Assoc. Comput. Mach. 10 (1963), 528–531.
H. S. Shank, Records of Turing machines,Math. Systems Theory 5 (1971), 50–55.
J. V. Uspensky andM. A. Heaslet,Elementary Number Theory, McGraw-Hill, New York, 1939.
H. Yamada, Real-time computation and recursive functions not real-time computable,IRE Trans. Electronic Computers EC-11 (1962), 753–760.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Cobham, A. Uniform tag sequences. Math. Systems Theory 6, 164–192 (1972). https://doi.org/10.1007/BF01706087
Received:
Issue date:
DOI: https://doi.org/10.1007/BF01706087