Magic Numbers in Periodic Sequences

DOI10.1007/978-3-031-33180-0_16arXiv2304.03268OpenAlexW4381303882MaRDI QIDQ6134875FDOQ6134875

Savinien Kreczman, Eric Rowland, Manon Stipulanti, Luca Prigioniero

Publication date: 25 July 2023

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The ring of \(k\)-regular sequences
• On the State Complexity of Complements, Stars, and Reversals of Regular Languages
• Automatic Sequences
• Uniform tag sequences
• Weak Second‐Order Arithmetic and Finite Automata
• The crystallographic restriction in higher dimensions
• Magic numbers in the state hierarchy of finite automata
• Deterministic blow-ups of minimal NFA's
• A family of NFAs which need 2\(^{n}-\alpha\) deterministic states
• Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs
• The magic number problem for subregular language families
• MAGIC NUMBERS AND TERNARY ALPHABET
• A decision method for the recognizability of sets defined by number systems
• Complexity of automatic sequences
• Decision Problems for Linear Recurrence Sequences
• Minimal DFA for testing divisibility
• An efficient algorithm to decide periodicity of b-recognisable sets using MSDF convention

   Recommendations

• Periodic sequences modulo 1 and Pisot numbers 👍 👎
• Title not available (Why is that?) 👍 👎
• 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 👍 👎
• Title not available (Why is that?) 👍 👎
• A remarkable sequence of integers 👍 👎
• Title not available (Why is that?) 👍 👎

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)