Unpublished conference/Abstract (Scientific congresses and symposiums)
Magic Numbers in Periodic Sequences
Stipulanti, Manon
2023Developments in Language Theory 2023 and WORDS 2023


Full Text
Author postprint (1.26 MB)

All documents in ORBi are protected by a user license.

Send to


Keywords :
Magic numbers; Muggle 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 :
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 :
12 June 2023
Number of pages :
Event name :
Developments in Language Theory 2023 and WORDS 2023
Event organizer :
Umeå University
Event place :
Umeå, Sweden
Event date :
June 12 to 16, 2023
Audience :
Funders :
F.R.S.-FNRS - Fonds de la Recherche Scientifique [BE]
Commentary :
Joint work with Savinien Kreczman (ULiège, Belgium), Luca Prigioniero (UNIMI, Italy), and Eric Rowland (Hofstra University, USA)
Available on ORBi :
since 12 June 2023


Number of views
38 (7 by ULiège)
Number of downloads
34 (1 by ULiège)


Similar publications

Contact ORBi