Automaticity IV : sequences, sets, and diversity

Jeffrey Shallit

Journal de théorie des nombres de Bordeaux (1996)

  • Volume: 8, Issue: 2, page 347-367
  • ISSN: 1246-7405

Abstract

top
This paper studies the descriptional complexity of (i) sequences over a finite alphabet ; and (ii) subsets of N (the natural numbers). If ( s ( i ) ) i ≥ 0 is a sequence over a finite alphabet Δ , then we define the k -automaticity of s , A s k ( n ) , to be the smallest possible number of states in any deterministic finite automaton that, for all i with 0 ≤ i ≤ n , takes i expressed in base k as input and computes s ( i ) . We give examples of sequences that have high automaticity in all bases k ; for example, we show that the characteristic sequence of the primes has k -automaticity A s k ( n ) = Ω ( n 1 / 43 ) for all k ≥ 2 , thus making quantitative the classical theorem of Minsky and Papert that the set of primes expressed in base 2 is not regular. We give examples of sequences with low automaticity in all bases k , and low automaticity in some bases and high in others. We also obtain bounds on the automaticity of certain sequences that are fixed points of homomorphisms, such as the Fibonacci and Thue-Morse infinite words. Finally, we define a related concept called diversity and give examples of sequences with high diversity.

How to cite

top

Shallit, Jeffrey. "Automaticity IV : sequences, sets, and diversity." Journal de théorie des nombres de Bordeaux 8.2 (1996): 347-367. <http://eudml.org/doc/247841>.

@article{Shallit1996,
abstract = {This paper studies the descriptional complexity of (i) sequences over a finite alphabet ; and (ii) subsets of $N$ (the natural numbers). If $(s(i))_\{i\ge 0\}$ is a sequence over a finite alphabet $\Delta $, then we define the $k$-automaticity of $s , A_s^k( n)$, to be the smallest possible number of states in any deterministic finite automaton that, for all $i$ with $0 \le i \le n$, takes $i$ expressed in base $k$ as input and computes $s(i)$. We give examples of sequences that have high automaticity in all bases $k$ ; for example, we show that the characteristic sequence of the primes has $k$-automaticity $A_s^k( n) = \Omega (n^\{1/43\})$ for all $k \ge 2$, thus making quantitative the classical theorem of Minsky and Papert that the set of primes expressed in base $2$ is not regular. We give examples of sequences with low automaticity in all bases $k$, and low automaticity in some bases and high in others. We also obtain bounds on the automaticity of certain sequences that are fixed points of homomorphisms, such as the Fibonacci and Thue-Morse infinite words. Finally, we define a related concept called diversity and give examples of sequences with high diversity.},
author = {Shallit, Jeffrey},
journal = {Journal de théorie des nombres de Bordeaux},
keywords = {measure of automaticity; characteristic sequence of the primes; diversity; -automaticity; finite automaton; Minsky Papert theorem},
language = {eng},
number = {2},
pages = {347-367},
publisher = {Université Bordeaux I},
title = {Automaticity IV : sequences, sets, and diversity},
url = {http://eudml.org/doc/247841},
volume = {8},
year = {1996},
}

TY - JOUR
AU - Shallit, Jeffrey
TI - Automaticity IV : sequences, sets, and diversity
JO - Journal de théorie des nombres de Bordeaux
PY - 1996
PB - Université Bordeaux I
VL - 8
IS - 2
SP - 347
EP - 367
AB - This paper studies the descriptional complexity of (i) sequences over a finite alphabet ; and (ii) subsets of $N$ (the natural numbers). If $(s(i))_{i\ge 0}$ is a sequence over a finite alphabet $\Delta $, then we define the $k$-automaticity of $s , A_s^k( n)$, to be the smallest possible number of states in any deterministic finite automaton that, for all $i$ with $0 \le i \le n$, takes $i$ expressed in base $k$ as input and computes $s(i)$. We give examples of sequences that have high automaticity in all bases $k$ ; for example, we show that the characteristic sequence of the primes has $k$-automaticity $A_s^k( n) = \Omega (n^{1/43})$ for all $k \ge 2$, thus making quantitative the classical theorem of Minsky and Papert that the set of primes expressed in base $2$ is not regular. We give examples of sequences with low automaticity in all bases $k$, and low automaticity in some bases and high in others. We also obtain bounds on the automaticity of certain sequences that are fixed points of homomorphisms, such as the Fibonacci and Thue-Morse infinite words. Finally, we define a related concept called diversity and give examples of sequences with high diversity.
LA - eng
KW - measure of automaticity; characteristic sequence of the primes; diversity; -automaticity; finite automaton; Minsky Papert theorem
UR - http://eudml.org/doc/247841
ER -

References

top
  1. [1] D. Allen, Jr. On a characterization of the nonregular set of primes. J. Comput. System Sci.2 (1968), 464-467. Zbl0177.01903MR243939
  2. [2] J.-P. Allouche, A. Arnold, J. Berstel, S. Brlek, W. Jockusch, S. Plouffe, and B.E. Sagan.A relative of the Thue-Morse sequence. Discrete Math.139 (1995), 455-461. Zbl0839.11007MR1336854
  3. [3] J. Berstel.Recent results on Sturmian words. To appear, Proc. of DLT '95. Also available at http://www-litp.ibpfr/berstel/Liaisons/magdeburg.ps.gz. 
  4. [4] J.W.S. Cassels.An Introduction to Diophantine Approximation. Cambridge University Press,1957. Zbl0077.04801MR87708
  5. [5] A. Cobham.Uniform tag sequences. Math. Systems Theory6 (1972),164-192. Zbl0253.02029MR457011
  6. [6] D. Crisp, W. Moran, A. Pollington, and P. Shiue.Substitution invariant cutting sequences. J. Théorie Nombres Bordeaux5 (1993),123-137. Zbl0786.11041MR1251232
  7. [7] C. Dwork and L. Stockmeyer.On the power of 2-way probabilistic finite state automata. In Proc. 30th Ann. Symp. Found. Comput. Sci., pages 480-485. IEEE Press, 1989. 
  8. [8] C. Dwork and L. Stockmeyer.A time complexity gap for two-way probabilistic finite-state automata. SIAM J. Comput.19 (1990), 1011-1023. Zbl0711.68075MR1069095
  9. [9] S. Eilenberg.Automata, Languages, and Machines, Vol. A. Academic Press, 1974. Zbl0317.94045MR530382
  10. [10] I. Glaister and J. Shallit.Automaticity III: Polynomial automaticity and context-free languages. Submitted,1996. Zbl0973.11031
  11. [11] G.H. Hardy and E.M. Wright.An Introduction to the Theory of Numbers. Oxford University Press, 1989. Zbl0020.29201MR568909
  12. [12] J. Hartmanis and H. Shank.On the recognition of primes by automata. J. Assoc. Comput. Mach.15 (1968), 382-389. Zbl0164.05201MR235916
  13. [13] D.R. Heath-Brown.The least square-free number in an arithmetic progression. J. Reine Angew. Math.332 (1982), 204-220. Zbl0493.10045MR656864
  14. [14] D.R. Heath-Brown.Zero-free regions for Dirichlet L-functions and the least prime in an arithmetic progression. Proc. Lond. Math. Soc.64 (1992), 265-338. Zbl0739.11033MR1143227
  15. [15] J.E. Hopcroft and J.D. Ullman.Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979. Zbl0426.68001MR645539
  16. [16] J. Kaneps and R. Freivalds.Minimal nontrivial space complexity of probabilistic one-way Turing machines. In B. Rovan, editor, MFCS '90 (Mathematical Foundations of Computer Science), Vol. 452 of Lecture Notes in Computer Science, pages 355-361. Springer-Verlag, 1990. Zbl0762.68019MR1084853
  17. [17] J. Kaneps and R. Freivalds.Running time to recognize nonregular languages by 2-way probabilistic automata. In J. Leach Albert, B. Monien, and M. Rodríguez Artalejo, editors, ICALP '91 (18th International Colloquium on Automata, Languages, and Programming), Vol. 510 of Lecture Notes in Computer Science, pages 174-185. Springer-Verlag, 1991. Zbl0766.68098MR1129905
  18. [18] D.E. Knuth.The Art of Computer Programming, Vol. III: Sorting and Searching. Addison-Wesley, 1973. Zbl0302.68010MR378456
  19. [19] M. Minsky and S. Papert.Unrecognizable sets of numbers. J. Assoc. Comput. Mach.13 (1966), 281-286. Zbl0166.00601MR207481
  20. [20] C. Pomerance, J.M. Robson, and J.O. Shallit.Automaticity II: Descriptional complexity in the unary case. To appear, Theoret. Comput. Sci. Zbl0959.11015MR1453865
  21. [21] J.B. Rosser and L. Schoenfeld.Approximate formulas for some functions of prime numbers. Ill. J. Math.6 (1962), 64-94. Zbl0122.05001MR137689
  22. [22] L. Schoenfeld.Sharper bounds for the Chebyshev functions θ(x) and ψ(x). II. Math. Comp.30 (1976), 337-360. Corrigenda in Math. Comp.30 (1976), 900. Zbl0326.10037
  23. [23] J. Shallit.Some facts about continued fractions that should be better known. Technical Report CS-91-30, University of Waterloo, Department of Computer Science, July 1991. 
  24. [24] J. Shallit.The fixed point of 1→ 121, 2 → 12221 is not 2-automatic. Unpublished manuscript, dated September 10, 1992. 
  25. [25] J. Shallit.Real numbers with bounded partial quotients: a survey. Enseign. Math.38 (1992),151-187. Zbl0753.11006MR1175525
  26. [26] J. Shallit and Y. Breitbart.Automaticity: Properties of a measure of descriptional complexity. In P. Enjalbert, E. W. Mayr, and K. W. Wagner, editors, STACS 94: 11th Annual Symposium on Theoretical Aspects of Computer Science, Vol. 775 of Lecture Notes in Computer Science, pages 619-630. Springer-Verlag, 1994. Zbl0859.68059MR1288529
  27. [27] J. Shallit and Y. Breitbart.Automaticity I: Properties of a measure of descriptional complexity. To appear, J. Comput. System Sci. Zbl0859.68059MR1409007
  28. [28] N.B. Slater.Gaps and steps for the sequence nθ mod 1. Proc. Cambridge Phil. Soc.63 (1967), 1115-1123. Zbl0178.04703
  29. [29] V.T. Sós.On the distribution mod 1 of the sequence nα. Ann. Univ. Sci. Budapest Eötvös Sect. Math.1 (1958),127-134. Zbl0094.02903
  30. [30] S. Swierczkowski.On successive settings of an arc on the circumference of a circle. Fundamenta Math.46 (1958), 187-189. Zbl0085.27203MR104651
  31. [31] S.S. Wagstaff, Jr. Greatest of the least primes in arithmetic progressions having a given modulus. Math. Comp.33 (1979), 1073-1080. Zbl0407.10034MR528061

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.