[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 :
Mathematics
Author, co-author :
Stipulanti, Manon ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
Magic Numbers in Periodic Sequences
Publication date :
12 June 2023
Number of pages :
22
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 :
International
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)
