Thue-Morse set; Automaton; State complexity; Formal language; Multiplication by a constant
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 sometimes called the evil numbers. We obtain an exact formula for the state complexity (i.e. the number of states of its minimal automaton) of the multiplication by a constant of the Thue-Morse set with respect to any integer 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 mT for any positive integers m and p. The used 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 some multiple of the Thue-Morse set.
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 :
State Complexity of the Multiples of the Thue-Morse Set
Alternative titles :
[fr] Complexité en états des multiples de l'ensemble de Thue-Morse
Publication date :
18 September 2019
Event name :
The Tenth International Symposium on Games, Automata, Logics, and Formal Verification (GandALF 2019)
Event place :
Bordeaux, France
Event date :
du 2 septembre 2019 au 3 septembre 2019
Audience :
International
Journal title :
Electronic Proceedings in Theoretical Computer Science
eISSN :
2075-2180
Publisher :
Open Publishing Association, Sydney, Australia
Special issue title :
Proceedings Tenth International Symposium on Games, Automata, Logics, and Formal Verification
Volume :
305
Pages :
34-49
Peer reviewed :
Peer Reviewed verified by ORBi
Funders :
F.R.S.-FNRS - Fonds de la Recherche Scientifique [BE]
Boris Alexeev (2004): Minimal DFA for testing divisibility. J. Comput. System Sci. 69(2), pp. 235-243, doi:10.1016/j.jcss.2004.02.001.
Jean-Paul Allouche (2015): Thue, Combinatorics on words, and conjectures inspired by the Thue-Morse sequence. Journal de Théorie des Nombres de Bordeaux 27, pp. 375-388, doi:10.5802/jtnb.906.
Jean-Paul Allouche, Narad Rampersad & Jeffrey Shallit (2009): Periodicity, repetitions, and orbits of an automatic sequence. Theoret. Comput. Sci. 410(30-32), pp. 2795-2803, doi:10.1016/j.tcs.2009.02.006.
Jean-Paul Allouche & Jeffrey Shallit (1992): The ring of k-regular sequences. Theoret. Comput. Sci. 98(2), pp. 163-197, doi:10.1016/S0304-3975(03)00090-2.
Bernard Boigelot, Isabelle Mainz, Victor Marsault & Michel Rigo (2017): An efficient algorithm to decide periodicity of b-recognisable sets using MSDF convention. In: 44th International Colloquium on Automata, Languages, and Programming, LIPIcs. Leibniz Int. Proc. Inform. 80, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, pp. Art. No. 118, 14, doi:10.4230/LIPIcs.ICALP.2017.118.
Bernard Boigelot, Stéphane Rassart & Pierre Wolper (1998): On the expressiveness of real and integer arithmetic automata (extended abstract). In: ICALP, Lecture Notes in Comput. Sci. 1443, Springer, Berlin, pp. 152-163, doi:10.1007/BFb0055049.
Véronique Bruyère & Georges Hansel (1997): Bertrand numeration systems and recognizability. Theoret. Comput. Sci. 181(1), pp. 17-43, doi:10.1016/S0304-3975(96)00260-5. Latin American Theoretical INformatics (Valparaíso, 1995).
Véronique Bruyère, Georges Hansel, Christian Michaux & Roger Villemaire (1994): Logic and p-Recognizable Sets of Integers. Bull. Belg. Math. Soc. Simon Stevin 1(2), pp. 191-238. Journées Montoises (Mons, 1992).
Émilie Charlier (2018): First-order logic and numeration systems. In: Sequences, groups, and number theory, Trends Math., Birkhäuser/Springer, Cham, pp. 89-141, doi:10.1016/0022-0000(83)90051-X.
Émilie Charlier, Célia Cisternino & Adeline Massuir (2019): State complexity of the multiples of the Thue-Morse set. Available at https://arxiv.org/abs/1903.06114. Full version.
Émilie Charlier, Julien Leroy & Michel Rigo (2015): An analogue of Cobham's theorem for graph directed iterated function systems. Adv. Math. 280, pp. 86-120, doi:10.1016/j.aim.2015.04.008.
Émilie Charlier & Narad Rampersad (2011): The growth function of S-recognizable sets. Theoret. Comput. Sci. 412(39), pp. 5400-5408, doi:10.1016/j.tcs.2011.05.057.
Émilie Charlier, Narad Rampersad, Michel Rigo & Laurent Waxweiler (2011): The minimal automaton recognizing mN in a linear numeration system. Integers 11B, pp. Paper No. A4, 24.
Émilie Charlier, Narad Rampersad & Jeffrey Shallit (2012): Enumeration and decidable properties of automatic sequences. Internat. J. Found. Comput. Sci. 23(5), pp. 1035-1066, doi:10.1142/S0129054112400448.
Alan Cobham (1969): On the Base-Dependence of Sets of Numbers Recognizable by Finite Automata. Math. Systems Theory 3, pp. 186-192, doi:10.1007/BF01746527.
Alan Cobham (1972): Uniform tag sequences. Math. Systems Theory 6, doi:10.1007/BF01706087.
Fabien Durand (2013): Decidability of the HD0L ultimate periodicity problem. RAIRO Theor. Inform. Appl. 47(2), pp. 201-214, doi:10.1051/ita/2013035.
Samuel Eilenberg (1974): Automata, languages, and machines. Vol. A. Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York. Pure and Applied Mathematics, Vol. 58.
Christiane Frougny (1992): Representations of numbers and finite automata. Math. Systems Theory 25(1), pp. 37-60, doi:10.1007/BF01368783.
Christiane Frougny & Jacques Sakarovitch (2010): Number representation and finite automata. In: Combinatorics, automata and number theory, Encyclopedia Math. Appl. 135, Cambridge Univ. Press, Cambridge, pp. 34-107, doi:10.1017/CBO9780511777653.003.
Juha Honkala (1986): A decision method for the recognizability of sets defined by number systems. RAIRO Inform. Théor. Appl. 20(4), pp. 395-403, doi:10.1051/ita/1986200403951.
John Hopcroft (1971): An n log n algorithm for minimizing states in a finite automaton. In: Theory of machines and computations (Proc. Internat. Sympos., Technion, Haifa, 1971), Academic Press, New York, pp. 189-196, doi:10.1016/B978-0-12-417750-5.50022-1.
John Hopcroft & Richard Karp (1971): A linear algorithm for testing equivalence of finite automata. Technical Report 71-114, University of California.
Jérôme Leroux (2005): A polynomial time Presburger criterion and synthesis for number decision diagrams. In: 20th IEEE Symposium on Logic in Computer Science, IEEE Computer Society, Chicago, IL, USA, pp. 147-156, doi:10.1109/LICS.2005.2.
M. Lothaire (1997): Combinatorics on words. Cambridge Mathematical Library, Cambridge University Press, Cambridge, doi:10.1017/CBO9780511566097.
Victor Marsault & Jacques Sakarovitch (2013): Ultimate periodicity of b-recognisable sets: a quasilinear procedure. In: Developments in language theory, Lecture Notes in Comput. Sci. 7907, Springer, Heidelberg, pp. 362-373, doi:10.1007/978-3-642-38771-5_32.
Ivan V. Mitrofanov (2013): Periodicity of morphic words. Fundam. Prikl. Mat. 18(4), pp. 107-119.
Hamoon Mousavi (2015): Walnut. Available at https://cs.uwaterloo.ca/~shallit/papers.html.
Andrei A. Muchnik (2003): The definable criterion for definability in Presburger arithmetic and its applications. Theoret. Comput. Sci. 290(3), pp. 1433-1444, doi:10.1016/S0304-3975(02)00047-6.
Michel Rigo (2014): Formal languages, automata and numeration systems. 2. Networks and Telecommunications Series, ISTE, London; John Wiley & Sons, Inc., Hoboken, NJ. Applications to recognizability and decidability, With a foreword by Valérie Berthé.
Jacques Sakarovitch (2009): Elements of automata theory. Cambridge University Press, Cambridge, doi:10.1017/CBO9781139195218. Translated from the 2003 French original by Reuben Thomas.
Jeffrey Shallit (2015): Enumeration and automatic sequences. Pure Math. Appl. (PU.M.A.) 25(1), pp. 96-106.
Laurent Waxweiler (2009): Caractère reconnaissable d'ensembles de polynômes à coefficients dans un corps fini. Ph.D. thesis, University of Liège, Belgium.
