Magic Numbers in Periodic Sequences

DOI10.1007/978-3-031-33180-0_16MaRDI QIDQ6134875zbMATH OpenOpenAlexFDO

Authors Savinien Kreczman, Luca Prigioniero, Eric Rowland, Manon Stipulanti

Publication date 25 July 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2304.03268

zbMATH Keywords

automatic sequencesregular sequencesperiodic sequencesmagic numbersconstant-recursive sequences

Mathematics Subject Classification ID

Combinatorics on words (68R15)

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,2^n] 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.

Recommendations

• Periodic sequences modulo 1 and Pisot numbers
• scientific article; zbMATH DE number 2113523
• Periodic sequences of numbers in generalized arithmetic and geometric alternate progressions
• Divisor matrices and magic sequences
• Magic Cubes and Prouhet Sequences
• Some fascinating integer sequences
• scientific article; zbMATH DE number 2187942
• A remarkable sequence of integers
• scientific article; zbMATH DE number 1919523

Cites work

• scientific article; zbMATH DE number 1973372 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 7089069 (Why is no real title available?)
• A decision method for the recognizability of sets defined by number systems
• A family of NFAs which need 2\(^{n}-\alpha\) deterministic states
• Abstract algebra
• An efficient algorithm to decide periodicity of \(b\)-recognisable sets using MSDF convention
• Automatic Sequences
• Complexity of automatic sequences
• Decision problems for linear recurrence sequences
• Deterministic blow-ups of minimal NFA's
• Magic numbers and ternary alphabet
• Magic numbers in the state hierarchy of finite automata
• Minimal DFA for testing divisibility
• Noncommutative rational series with applications
• On the State Complexity of Complements, Stars, and Reversals of Regular Languages
• The crystallographic restriction in higher dimensions
• The magic number problem for subregular language families
• The ring of \(k\)-regular sequences
• Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs
• Uniform tag sequences
• Weak Second‐Order Arithmetic and Finite Automata

This page was built for publication: Magic Numbers in Periodic Sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6134875)