State Complexity of Testing Divisibility
classification
💻 cs.FL
keywords
acceptingautomatoncomplexitygreedyminimalmultiplesrepresentationsstate
read the original abstract
Under some mild assumptions, we study the state complexity of the trim minimal automaton accepting the greedy representations of the multiples of m >= 2 for a wide class of linear numeration systems. As an example, the number of states of the trim minimal automaton accepting the greedy representations of the multiples of m in the Fibonacci system is exactly 2m^2.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.