Numeration Systems: a Link between Number Theory and Formal Language Theory

Rigo, Michel

doi:10.1007/978-3-642-14455-4_6

Request a copy

Paper published in a journal (Scientific congresses and symposiums)

Numeration Systems: a Link between Number Theory and Formal Language Theory

Rigo, Michel

2010 • In Lecture Notes in Computer Science, 6224, p. 33-53

Permalink
https://hdl.handle.net/2268/35488

DOI
10.1007/978-3-642-14455-4_6

Files (2)Send to Details Statistics Bibliography Similar publications

Files

Full Text

survey-v2.pdf

Author preprint (213.44 kB)

Request a copy

Annexes

RigoDLT.pdf

Publisher postprint (919.23 kB)

slides of the invited talk

Download

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

Numeration system; Cobham's theorem; Number Theory

Abstract :

[en] We survey facts mostly emerging from the seminal results of Alan Cobham obtained in the late sixties and early seventies. We do not attempt to be exhaustive but try instead to give some personal interpretations and some research directions. We discuss the notion of numeration systems, recognizable sets of integers and automatic sequences. We brie y sketch some results about transcendence related to the representation of real numbers. We conclude with some applications to combinatorial game theory and veri cation of in nite-state systems and present a list of open problems.

Disciplines :

Computer science
Mathematics

Author, co-author :

Rigo, Michel ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes

Language :

English

Title :

Numeration Systems: a Link between Number Theory and Formal Language Theory

Publication date :

2010

Event name :

Developments in Language Theory

Event place :

London, Ontario, Canada

By request :

Yes

Audience :

International

Journal title :

Lecture Notes in Computer Science

ISSN :

0302-9743

eISSN :

1611-3349

Publisher :

Springer, Berlin, Germany

Volume :

6224

Pages :

33-53

Available on ORBi :

since 12 May 2010

Statistics

Number of views

172 (15 by ULiège)

Number of downloads

96 (7 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

Bibliography

Adamczewski, B., Bell, J. P.: An analogue of Cobham's theorem for fractals. Trans. Amer. math. Soc. (to appear)
Adamczewski, B., Bell, J. P.: Automata in number theory. In: Pin, J.-E. (ed.) Handbook, Automata: from Mathematics to Applications. Europ. Math. Soc. Publishing House (to appear)
Adamczewski, B., Bugeaud, Y.: On the complexity of algebraic numbers I: Expansion in integer bases. Ann. of Math. 165, 547-565 (2007)
Adamczewski, B., Bugeaud, Y., Luca, F.: Sur la complexité des nombres algébriques. C. R. Math. Acad. Sci. Paris 339, 11-14 (2004)
Adamczewski, B., Rampersad, N.: On patterns occurring in binary algebraic numbers. Proc. Amer. Math. Soc. 136, 3105-3109 (2008)
Akiyama, S., Frougny, C., Sakarovitch, J.: Powers of rationals modulo 1 and rational base number systems. Israel J. Math. 168, 53-91 (2008)
Alexeev, B.: Minimal DFA for testing divisibility. J. Comput. System Sci. 69(2), 235-243 (2004)
Allouche, J.-P.: Sur la complexité des suites infinies. Bull. Belg. Math. Soc. 1, 133-143 (1994)
Allouche, J.-P., Cateland, E., Gilbert, W. J., Peitgen, H.-O., Shallit, J., Skordev, G.: Automatic maps in exotic numeration systems. Theory Comput. Systems 30, 285-331 (1997)
Allouche, J.-P., Shallit, J., Skordev, G.: Self-generating sets, integers with missing blocks, and substitutions. Discrete Math. 292 (1-3), 1-15 (2005)
Allouche, J.-P., Shallit, J. O.: The ubiquitous Prouhet-Thue-Morse sequence. In: Ding, C., Helleseth, T., Niederreiter, H. (eds.) Sequences and Their Applications, Proceedings of SETA 1998, pp. 1-16. Springer, Heidelberg (1999)
Allouche, J.-P., Shallit, J. O.: Automatic Sequences, Theory, Applications, Generalizations. Cambridge University Press, Cambridge (2003)
Barat, G., Berthé, V., Liardet, P., Thuswaldner, J.: Dynamical directions in numeration. Ann. Inst. Fourier (Grenoble) 56, 1987-2092 (2006)
Béal, M.-P., Lombardy, S., Sakarovitch, J.: Conjugacy and equivalence if weighted automata and functional transducers. In: Grigoriev, D., Harrison, J., Hirsch, E. A. (eds.) CSR 2006. LNCS, vol. 3967, pp. 58-69. Springer, Heidelberg (2006)
Berge, C.: Graphes et hypergraphes. Dunod, Paris, Deuxième édition, Collection Dunod Université, Série Violette, No. 604(1973)
Berlekamp, E. R., Conway, J. H., Guy, R. K.: Winning ways for your mathematical plays, 2nd edn., vol. 1. A. K. Peters Ltd., Natick (2001)
Berstel, J., Karhumäki, J.: Combinatorics on words: a tutorial. Bull. European Assoc. Theor. Comput. Sci. 79, 178-228 (2003)
Berthé, V.: Autour du système de numération d'Ostrowski. Bull. Belg. Math. Soc. Simon Stevin 8, 209-239 (2001)
Berthé, V., Rigo, M. (eds.): Combinatorics, Automata and Number Theory. Encyclopedia of Mathematics and its Applications, vol. 135. Cambridge University Press, Cambridge (2010)
Berthé, V., Siegel, A.: Tilings associated with beta-numeration and substitutions. Integers 5(3):A2, 46(2005) (electronic)
Boigelot, B., Bronne, L., Rassart, S.: An improved reachability analysis method for strongly linear hybrid systems. In: Grumberg, O. (ed.) CAV 1997. LNCS, vol. 1254, pp. 167-177. Springer, Heidelberg (1997)
Boigelot, B., Brusten, J.: A generalization of Cobham's theorem to automata over real numbers. Theoret. Comput. Sci. 410(18), 1694-1703 (2009)
Boigelot, B., Brusten, J., Leroux, J.: A generalization of Semenov's theorem to automata over real numbers. In: Schmidt, R. A. (ed.) Automated Deduction - CADE-22. LNCS, vol. 5663, pp. 469-484. Springer, Heidelberg (2009)
Boigelot, B., Jodogne, S., Wolper, P.: An effective decision procedure for linear arithmetic over the integers and reals. ACM Trans. Comput. Log. 6(3), 614-633 (2005)
Boigelot, B., Rassart, S., Wolper, P.: On the expressiveness of real and integer arithmetic automata. In: Larsen, K. G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol. 1443, pp. 152-163. Springer, Heidelberg (1998)
Boyd, D. W.: Irreducible polynomials with many roots of maximal modulus. Acta Arith. 68(1), 85-88 (1994)
Brlek, S.: Enumeration of factors in the Thue-Morse word. Discrete Appl. Math. 24, 83-96 (1989)
Bruyère, V., Hansel, G.: Bertrand numeration systems and recognizability. Theoret. Comput. Sci. 181, 17-43 (1997)
Bruyère, V., Hansel, G., Michaux, C., Villemaire, R.: Logic and p-recognizable sets of integers. Bull. Belg. Math. Soc. 1, 191-238 (1994)
Bugeaud, Y., Evertse, J.-H.: On two notions of complexity of algebraic numbers. Acta Arith. 133, 221-250 (2008)
Charlier, E., Kärki, T., Rigo, M.: Multidimensional generalized automatic sequences and shape-symmetric morphic words. Discrete Math. 310, 1238-1252 (2010)
Charlier, E., Rampersad, N., Rigo, M., Waxweiler, L.: State complexity of testing divisibility (2010) (preprint)
Charlier, E., Rigo, M., Steiner, W.: Abstract numeration systems on bounded languages and multiplication by a constant. Integers 8 (A35), 19(2008)
Choffrut, C., Karhumäki, J.: Combinatorics of words. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of formal languages, Word, Language, Grammar, vol. 1, pp. 329-438. Springer, New York (1997)
Cobham, A.: On the Hartmanis-Stearns problem for a class of tag machines. In: IEEE Conference Record of 1968 Ninth Annual Symposium on Switching and Automata Theory, pp. 51-60 (1968)
Cobham, A.: On the base-dependence of sets of numbers recognizable by finite automata. Math. Systems Theory 3, 186-192 (1969)
Cobham, A.: Uniform tag sequences. Math. Systems Theory 6, 164-192 (1972)
Crisp, D., Moran, W., Pollington, A., Shiue, P.: Substitution invariant cutting sequences. J. Théor. Nombres Bordeaux 5(1), 123-137 (1993)
de Luca, A., Varricchio, S.: On the factors of the Thue-Morse word on three symbols. Inform. Process. Lett. 27, 281-285 (1988)
Derksen, H.: A Skolem-Mahler-Lech theorem in positive characteristic and finite automata. Invent. Math. 168, 175-224 (2007)
Duchêne, E., Fraenkel, A. S., Nowakowski, R., Rigo, M.: Extensions and restrictions of Wythoff's game preserving Wythoff's sequence as set of P-positions. J. Combinat. Theory Ser. A 117, 545-567 (2010)
Duchêne, E., Rigo, M.: Invariant games. Theoret. Comput. Sci. (to appear)
Duchêne, E., Rigo, M.: Cubic Pisot unit combinatorial games. Monat. für Math. 155, 217-249 (2008)
Duchêne, E., Rigo, M.: A morphic approach to combinatorial games: the tribonacci case. Theor. Inform. Appl. 42, 375-393 (2008)
Durand, F.: A generalization of Cobham's theorem. Theory Comput. Syst. 31(2), 169-185 (1998) (Pubitemid 128342343)
Durand, F.: Sur les ensembles d'entiers reconnaissables. J. Théor. Nombres Bordeaux 10(1), 65-84 (1998)
Durand, F.: A theorem of Cobham for non primitive substitutions. Acta Arith. 104, 225-241 (2002)
Durand, F., Rigo, M.: On Cobham's theorem. In: Handbook, Automata: from Mathematics to Applications. Europ. Math. Soc. Publishing House (to appear)
Durand, F., Rigo, M.: Syndeticity and independent substitutions. Adv. in Appl. Math. 42, 1-22 (2009)
Eilenberg, S.: Automata, Languages, and Machines, vol. A. Academic Press, London (1974)
Ferenczi, S., Mauduit, C.: Transcendence of numbers with a low complexity expansion. J. Number Theory 67, 146-161 (1997)
Fraenkel, A. S.: Complementary iterated floor words and the flora game. SIAM J. on Discrete Math. (to appear)
Fraenkel, A. S.: How to beat your Wythoff games' opponent on three fronts. Amer. Math. Monthly 89, 353-361 (1982)
Fraenkel, A. S.: Systems of numeration. Amer. Math. Monthly 92, 105-114 (1985)
Fraenkel, A. S.: The Sprague-Grundy function for Wythoff's game. Theoret. Comput. Sci. 75, 311-333 (1990)
Fraenkel, A. S.: Heap games, numeration systems and sequences. Annals of Combin. 2, 197-210 (1998)
Fraenkel, A. S.: Complexity, appeal and challenges of combinatorial games. Theoret. Comput. Sci. 313(3), 393-415 (2004)
Frougny, C.: Representations of numbers and finite automata. Math. Systems Theory 25, 37-60 (1992)
Frougny, C.: On the sequentiality of the successor function. Inform. and Comput. 139(1), 17-38 (1997)
Frougny, C., Solomyak, B.: Finite beta-expansions. Ergod. Th. & Dynam. Sys. 12, 713-723 (1992)
Grabner, P., Heuberger, C., Prodinger, H.: Distribution results for low-weight binary representations for pairs of integers. Theoret. Comput. Sci. 319, 307-331 (2004)
Hansel, G., Safer, T.: Vers un théorème de Cobham pour les entiers de Gauss. Bull. Belg. Math. Soc. Simon Stevin 10, 723-735 (2003)
Hardy, G. H., Wright, E. M.: An Introduction to the Theory of Numbers, 5th edn. Oxford University Press, Oxford (1985)
Hartmanis, J., Stearns, R. E.: On the computational complexity of algorithms. Trans. Amer. Math. Soc. 117, 285-306 (1965)
Hollander, M.: Greedy numeration systems and regularity. Theory Comput. Systems 31, 111-133 (1998) (Pubitemid 128342341)
Honkala, J.: On the simplification of infinite morphic words. Theoret. Comput. Sci. 410 (8-10), 997-1000 (2009)
Kärki, T., Lacroix, A., Rigo, M.: On the recognizability of self-generating sets. J. Integer Sequences, Article 10.2.2 (2010)
Kátai, I., Szabó, J.: Canonical number systems for complex integers. Acta Sci. Math (Szeged) 37 (3-4), 255-260 (1975)
Kimberling, C.: A self-generating set and the golden mean. J. Integer Seq., Article 00.2.8, 3(2) (2000)
Knuth, D. E.: The art of computer programming. In: Seminumerical algorithms, 2nd edn. Addison-Wesley Series in Computer Science and Information Processing, vol. 2, Addison-Wesley Publishing Co., Reading (1981)
Lecomte, P. B. A., Rigo, M.: Numeration systems on a regular language. Theory Comput. Systems 34, 27-44 (2001)
Lenstra, H.: Profinite Fibonacci numbers. Nieuw. Arch. Wiskd. (5) 6(4), 297-300 (2005);
Also in Europ. Math. Soc. Newsletter 61, 15-18 (September 2006)
Lind, D., Marcus, B.: An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, Cambridge (1995)
Löding, C.: Efficient minimization of deterministic weak ω-automata. Inform. Process. Lett. 79(3), 105-109 (2001)
Loraud, N.: β-shift, systèmes de numération et automates. J. Théorie Nombres Bordeaux 7, 473-498 (1995)
Lothaire, M.: Algebraic Combinatorics on Words. Encyclopedia of Mathematics and Its Applications, vol. 90. Cambridge University Press, Cambridge (2002)
Lothaire, M.: Applied Combinatorics on Words. Encyclopedia of Mathematics and Its Applications, vol. 105. Cambridge University Press, Cambridge (2005)
Michaux, C., Villemaire, R.: Open questions around Büchi and Presburger arithmetics. In: Logic: from Foundations to Applications (Staffordshire, 1993), pp. 353-383. Oxford Sci. Publ., New York (1996)
Pansiot, J.-J.: Complexité des facteurs des mots infinis engendrés par morphismes itérés. In: ICALP 1984. LNCS, vol. 172, pp. 380-389. Springer, Berlin (1984)
Parry, W.: On the β-expansions of real numbers. Acta Math. Acad. Sci. Hung. 11, 401-416 (1960)
Perrin, D.: Finite automata. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science. Formal Models and Semantics, vol. B, pp. 1-57. Elsevier/MIT Press (1990)
Pytheas Fogg, N.: Substitutions in Dynamics, Arithmetics and Combinatorics. In: Berthé, V., Ferenczi, S., Mauduit, C., Siegel, A. (eds.). LNM, vol. 1794. Springer, Heidelberg (2002)
Rigo, M., Maes, A.: More on generalized automatic sequences. J. Automata, Languages, and Combinatorics 7, 351-376 (2002)
Rigo, M., Waxweiler, L.: A note on syndeticity, recognizable sets and Cobham's theorem. Bull. European Assoc. Theor. Comput. Sci. 88, 169-173 (2006)
Sakarovitch, J.: Éléments de théorie des automates. Vuibert, English corrected edition: Elements of Automata Theory. Cambridge University Press, Cambridge (2003/2009)
Salon, O.: Suites automatiques à multi-indices. In: Séminaire de Théorie des Nombres de Bordeaux, pp. 4.01-4.27 (1986-1987)
Salon, O.: Suites automatiques à multi-indices et algébricité. C. R. Acad. Sci. Paris 305, 501-504 (1987)
Schmidt, W. M.: Diophantine Approximation. LNM, vol. 785. Springer, Heidelberg (1980)
Shallit, J. O.: Numeration systems, linear recurrences, and regular sets. Inform. Comput. 113, 331-347 (1994)
Silva, C. E.: Invitation to ergodic theory. Student Mathematical Library, vol. 42. American Mathematical Society, Providence (2008)
Waldschmidt, M.: Diophantine approximation on linear algebraic groups. Grundlehren der Mathematischen Wissenschaften, vol. 326. Springer, Berlin (2000); Transcendence properties of the exponential function in several variables
Waldschmidt, M.: Words and transcendence. In: Analytic Number Theory - Essays in Honour of Klaus Roth, ch. 31, pp. 449-470. Cambridge University Press, Cambridge (2009), http://arxiv.org/abs/0908.4034