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.
2023
 

Files


Full Text
paper-KPRS-submission.pdf
Author preprint (524.42 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



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 :
Mathematics
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 :
English
Title :
Magic numbers in periodic sequences
Publication date :
27 February 2023
Number of pages :
20
Funders :
F.R.S.-FNRS - Fonds de la Recherche Scientifique [BE]
Available on ORBi :
since 27 February 2023

Statistics


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

Bibliography


Similar publications



Contact ORBi