×

Uniform tag sequences. (English) Zbl 0253.02029


MSC:

03D03 Thue and Post systems, etc.
11B85 Automata sequences
Full Text: DOI

References:

[1] J. R. Büchi, Weak second-order arithmetic and finite automata,Z. Math. Logik Grundlagen Math. 6 (1960), 66–92. · Zbl 0103.24705 · doi:10.1002/malq.19600060105
[2] R. Bumby andE. Ellentuck, Finitely additive measures and the first digit problem,Fund. Math. 65 (1969), 33–42. · Zbl 0179.35601
[3] 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.
[4] A. Cobham, On the base-dependence of sets of numbers recognizable by finite automata,Math. Systems Theory 3 (1969), 186–192. · Zbl 0179.02501 · doi:10.1007/BF01746527
[5] B. D. Craven, On digital distribution in some integer sequences,J. Austral. Math. Soc. 5 (1965), 325–330. · Zbl 0144.27504 · doi:10.1017/S1446788700027750
[6] C. C. Elgot, Decision problems of finite automata design and related arithmetics,Trans. Amer. Math. Soc. 98 (1961), 21–51. · Zbl 0111.01102 · doi:10.1090/S0002-9947-1961-0139530-9
[7] P. C. Fischer, A. R. Meyer andA. L. Rosenberg, Time-restricted sequence generation,J. Comput. System Sci. 4 (1970), 50–73. · Zbl 0191.18301 · doi:10.1016/S0022-0000(70)80012-5
[8] B. J. Flehinger, On the probability that a random integer has initial digit A,Amer. Math. Monthly 73 (1966), 1056–1061. · Zbl 0147.17502 · doi:10.2307/2314636
[9] F. R. Gantmacher,The Theory of Matrices (2 vols.), Chelsea, New York, 1960. · Zbl 0088.25103
[10] S. Ginsburg,The Mathematical Theory of Context-Free Languages, McGraw-Hill, New York, 1966. · Zbl 0184.28401
[11] W. H. Gottschalk andG. A. Hedlund,Topological Dynamics, Amer. Math. Soc., Providence, R.I., 1955. · Zbl 0067.15204
[12] H. Halberstam andK. F. Roth,Sequences, Vol. I, Oxford Univ. Press, Oxford, 1966.
[13] G. H. Hardy andE. M. Wright,An Introduction to the Theory of Numbers, fourth edition, Oxford Univ. Press, Oxford, 1965. · Zbl 0020.29201
[14] J. Hartmanis andH. Shank, On the recognition of primes by automata,J. Assoc. Comput. Mach. 15 (1968), 328–389. · Zbl 0164.05201
[15] 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
[16] G. A. Hedlund, Remarks on the work of Axel Thue on sequences,Nordisk Mat. Tidskr. 15 (1967), 148–150. · Zbl 0153.33101
[17] G. A. Hedlund, Endomorphisms and automorphisms of the shift dynamical system,Math. Systems Theory 3 (1969), 320–375. · Zbl 0182.56901 · doi:10.1007/BF01691062
[18] L. Hellerman, W. L. Duda andS. Winograd, Continuity and realizability of sequence transformations,IEEE Trans. Electronic Computers EC-15 (1966), 560–569.
[19] M. Keane, Generalized Morse sequences,Z. Wahrscheinlichkeitstheorie Verw. Gebiete 10 (1968), 335–353. · Zbl 0162.07201 · doi:10.1007/BF00531855
[20] W. J. LeVeque,Topics in Number Theory (2 vols.), Addison-Wesley, Reading, Mass., 1956. · Zbl 0070.03804
[21] M. L. Minsky,Computation: Finite and Infinite Machines, Prentice-Hall, Englewood Cliffs, N.J., 1967. · Zbl 0195.02402
[22] M. Minsky andS. Papert, Unrecognizable sets of numbers,J. Assoc. Comput. Mach. 13 (1966), 281–286. · Zbl 0166.00601
[23] D. J. Newman, On the number of binary digits in a multiple of three,Proc. Amer. Math. Soc. 21 (1969), 719–721. · Zbl 0194.35004 · doi:10.1090/S0002-9939-1969-0244149-8
[24] 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
[25] G. N. Raney, Sequential functions,J. Assoc. Comput. Mach. 5 (1958), 177–180. · Zbl 0088.01801
[26] R. W. Ritchie, Finite automata and the set of squares,J. Assoc. Comput. Mach. 10 (1963), 528–531. · Zbl 0118.12601
[27] H. S. Shank, Records of Turing machines,Math. Systems Theory 5 (1971), 50–55. · Zbl 0214.01901 · doi:10.1007/BF01691466
[28] J. V. Uspensky andM. A. Heaslet,Elementary Number Theory, McGraw-Hill, New York, 1939. · Zbl 0022.30602
[29] H. Yamada, Real-time computation and recursive functions not real-time computable,IRE Trans. Electronic Computers EC-11 (1962), 753–760. · 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.