Thue-Morse set; Automaton; State complexity; Formal language; Multiplication by a constant; Translation
Abstract :
[en] The Thue-Morse set T is the set of those non-negative integers whose binary expansions have an even number of 1. The name of this set comes from the fact that its characteristic sequence is given by the famous Thue-Morse word abbabaabbaababba..., which is the fixed point starting with a of the word morphism a -> ab; b -> ba. The numbers in T are commonly called the evil numbers. We obtain an exact formula for the state complexity of the set mT + r (i.e. the number of states of its minimal automaton) with respect to any base b which is a power of 2. Our proof is constructive and we are able to explicitly provide the minimal automaton of the language of all 2^p-expansions of the set of integers mT +r for any positive integers p and m and any remainder r between 0 and m-1. The proposed method is general for any b-recognizable set of integers. As an application, we obtain a decision procedure running in quadratic time for the problem of deciding whether a given 2^p-recognizable set is equal to a set of the form mT + r.
Disciplines :
Mathematics
Author, co-author :
Charlier, Emilie ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Cisternino, Célia ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Massuir, Adeline ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
Minimal automaton for multiplying and translating the Thue-Morse set
Alternative titles :
[fr] Automate minimal pour multiplier et translater l'ensemble de Thue-Morse
Publication date :
2021
Journal title :
Electronic Journal of Combinatorics
ISSN :
1097-1440
eISSN :
1077-8926
Publisher :
Electronic Journal of Combinatorics, United States - Georgia
Volume :
28
Issue :
P3.12
Pages :
36
Peer reviewed :
Peer Reviewed verified by ORBi
Funders :
F.R.S.-FNRS - Fonds de la Recherche Scientifique [BE]
B. Alexeev. Minimal DFA for testing divisibility. J. Comput. System Sci., 69(2):235– 243, 2004.
J.-P. Allouche. Thue, combinatorics on words, and conjectures inspired by the Thue-Morse sequence. J. Théor. Nombres Bordeaux, 27:375–388, 2015.
J.-P. Allouche, B. Cloitre, and V. Shevelev. Beyond odious and evil. Aequationes Math., 90(2):341–353, 2016.
J.-P. Allouche, N. Rampersad, and J. Shallit. Periodicity, repetitions, and orbits of an automatic sequence. Theoret. Comput. Sci., 410(30-32):2795–2803, 2009.
J.-P. Allouche and J. Shallit. The ring of k-regular sequences. Theoret. Comput. Sci., 98(2):163–197, 1992.
J.-P. Allouche and J. Shallit. The ubiquitous Prouhet-Thue-Morse sequence. In Sequences and their applications (Singapore, 1998), Springer Ser. Discrete Math. Theor. Comput. Sci., pages 1–16. Springer, London, 1999.
J.-P. Allouche and J. Shallit. Automatic sequences. Cambridge University Press, Cambridge, 2003. Theory, applications, generalizations.
B. Boigelot, I. Mainz, V. Marsault, and M. Rigo. An efficient algorithm to decide periodicity of b-recognisable sets using MSDF convention. In 44th International Colloquium on Automata, Languages, and Programming, volume 80 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 118, 14. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2017.
B. Boigelot, S. Rassart, and P. Wolper. On the expressiveness of real and integer arithmetic automata (extended abstract). In ICALP, volume 1443 of Lecture Notes in Comput. Sci., pages 152–163. Springer, Berlin, 1998.
V. Bruyère and G. Hansel. Bertrand numeration systems and recognizability. Theoret. Comput. Sci., 181(1):17–43, 1997. Latin American Theoretical INformatics (Valparaíso, 1995).
V. Bruyère, G. Hansel, C. Michaux, and R. Villemaire. Logic and p-recognizable sets of integers. Bull. Belg. Math. Soc. Simon Stevin, 1(2):191–238, 1994. Journées Montoises (Mons, 1992).
M. Bucci, N. Hindman, S. Puzynina, and L. Q. Zamboni. On additive properties of sets defined by the Thue-Morse word. J. Combin. Theory Ser. A, 120(6):1235–1245, 2013.
É. Charlier. First-order logic and numeration systems. In Sequences, groups, and number theory, Trends Math., pages 89–141. Birkhäuser/Springer, Cham, 2018.
É. Charlier, C. Cisternino, and A. Massuir. State complexity of the multiples of the Thue-Morse set. In Tenth International Symposium on Games, Automata, Logics, and Formal Verification (GandALF 2019), volume 305 of Electronic Proceedings in Theoretical Computer Science, pages 34–49. Open Publishing Association, 2019.
É. Charlier, J. Leroy, and M. Rigo. An analogue of Cobham’s theorem for graph directed iterated function systems. Adv. Math., 280:86–120, 2015.
É. Charlier and N. Rampersad. The growth function of S-recognizable sets. Theoret. Comput. Sci., 412(39):5400–5408, 2011.
É. Charlier, N. Rampersad, M. Rigo, and L. Waxweiler. The minimal automaton recognizing mN in a linear numeration system. Integers, 11B:Paper No. A4, 24, 2011.
É. Charlier, N. Rampersad, and J. Shallit. Enumeration and decidable properties of automatic sequences. Internat. J. Found. Comput. Sci., 23(5):1035–1066, 2012.
A. Cobham. On the base-dependence of sets of numbers recognizable by finite automata. Math. Systems Theory, 3:186–192, 1969.
A. Cobham. Uniform tag sequences. Math. Systems Theory, 6, 1972.
F. Durand. Decidability of the HD0L ultimate periodicity problem. RAIRO Theor. Inform. Appl., 47(2):201–214, 2013.
S. Eilenberg. Automata, languages, and machines. Vol. A. Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York, 1974. Pure and Applied Mathematics, Vol. 58.
C. Frougny. Representations of numbers and finite automata. Math. Systems Theory, 25(1):37–60, 1992.
C. Frougny and J. Sakarovitch. Number representation and finite automata. In Combinatorics, automata and number theory, volume 135 of Encyclopedia Math. Appl., pages 34–107. Cambridge Univ. Press, Cambridge, 2010.
J. Honkala. A decision method for the recognizability of sets defined by number systems. RAIRO Inform. Théor. Appl., 20(4):395–403, 1986.
J. Leroux. A polynomial time Presburger criterion and synthesis for number decision diagrams. In 20th IEEE Symposium on Logic in Computer Science, pages 147–156. IEEE Computer Society, Chicago, IL, USA, 2005.
M. Lothaire. Combinatorics on words. Cambridge Mathematical Library. Cambridge University Press, Cambridge, 1997.
V. Marsault and J. Sakarovitch. Ultimate periodicity of b-recognisable sets: a quasilinear procedure. In Developments in language theory, volume 7907 of Lecture Notes in Comput. Sci., pages 362–373. Springer, Heidelberg, 2013.
V. Marsault. An efficient algorithm to decide periodicity of b-recognizable sets using LSDF convention. Log. Methods Comput. Sci., 15(3), 2019.
C. Mauduit. Multiplicative properties of the Thue-Morse sequence. Period. Math. Hungar., 43(1-2):137–153, 2001.
I. V. Mitrofanov. Periodicity of morphic words. Fundam. Prikl. Mat., 18(4):107–119, 2013.
H. Mousavi. Walnut. https://cs.uwaterloo.ca/~shallit/papers.html, 2015.
A. A. Muchnik. The definable criterion for definability in Presburger arithmetic and its applications. Theoret. Comput. Sci., 290(3):1433–1444, 2003.
M. Queffélec. Questions around the Thue-Morse sequence. Unif. Distrib. Theory, 13(1):1–25, 2018.
M. Rigo. Formal languages, automata and numeration systems. 2. Networks and Telecommunications Series. ISTE, London; John Wiley & Sons, Inc., Hoboken, NJ, 2014. Applications to recognizability and decidability, With a foreword by Valérie Berthé.
J. Sakarovitch. Elements of automata theory. Cambridge University Press, Cambridge, 2009. Translated from the 2003 French original by Reuben Thomas.
J. Shallit. Enumeration and automatic sequences. Pure Math. Appl. (PU.M.A.), 25(1):96–106, 2015.
L. Waxweiler. Caractère reconnaissable d’ensembles de polynômes à coefficients dans un corps fini. PhD thesis, University of Liège, Belgium, 2009.
