Eprint first made available on ORBi (E-prints, working papers and research blog)
Magic numbers in periodic sequences
Kreczman, Savinien; Luca Prigioniero; Eric Rowland et al.


Full Text
Author preprint (524.42 kB)

All documents in ORBi are protected by a user license.

Send to


Keywords :
Magic numbers; Periodic sequences; Automatic sequences; Regular sequences; Constant-recursive sequences
Abstract :
[en] In formal languages and automata theory, the magic number problem can be formulated as follows: for a given integer n, is it possible to find a number d in the range [n,2n] such that there is no minimal deterministic finite automaton with d states that can be simulated by an optimal nondeterministic finite automaton with exactly n states? If such a number d exists, it is called magic. In this paper, we consider the magic number problem in the framework of deterministic automata with output, which are known to characterize automatic sequences. More precisely, we characterize magic numbers for periodic sequences viewed as either automatic, regular, or constant-recursive.
Disciplines :
Author, co-author :
Kreczman, Savinien ;  Université de Liège - ULiège > Mathematics
Luca Prigioniero;  UNIMI - Università degli Studi di Milano [IT] > Dipartimento di Informatica
Eric Rowland;  Hofstra University > Department of Mathematics
Stipulanti, Manon  ;  Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
Title :
Magic numbers in periodic sequences
Publication date :
27 February 2023
Number of pages :
Funders :
F.R.S.-FNRS - Fonds de la Recherche Scientifique [BE]
Available on ORBi :
since 27 February 2023


Number of views
79 (16 by ULiège)
Number of downloads
95 (3 by ULiège)


Similar publications

Contact ORBi