Magic numbers in periodic sequences
Authors:
- Savinien KreczmanSKSavinien Kreczman
- Luca PrigionieroLPLuca Prigioniero
- Eric RowlandEREric Rowland
- Manon StipulantiMSManon Stipulanti
Preprint
Abstract
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 investigate magic numbers for periodic sequences viewed as either automatic, regular, or constant-recursive.Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Complexity of automatic sequencesInformation and Computation, 2022
- Decision Problems for Linear Recurrence Sequences2012
- On the State Complexity of Complements, Stars, and Reversals of Regular Languages2008
- Minimal DFA for testing divisibilityJournal of Computer and System Sciences, 2004
- A family of NFAs which need 2n−α deterministic statesTheoretical Computer Science, 2003
- Tight bounds on the number of states of DFAs that are equivalent to n-state NFAsTheoretical Computer Science, 2000
- The ring of k-regular sequencesTheoretical Computer Science, 1992
- A decision method for the recognizability of sets defined by number systemsRAIRO - Theoretical Informatics and Applications, 1986
- Uniform tag sequencesTheory of Computing Systems, 1972
- Weak Second‐Order Arithmetic and Finite AutomataMathematical Logic Quarterly, 1960