Minimal DFAs for Testing Divisibility
arXiv:cs/0309052 · doi:10.1016/j.jcss.2004.02.001
Abstract
We present and prove a theorem answering the question "how many states does a minimal deterministic finite automaton (DFA) that recognizes the set of base-b numbers divisible by k have?"
LaTeX, 7 pages (corrected typo in new version)
Cited by in corpus (6)
- Proceedings Twelfth Annual Workshop on Descriptional Complexity of Formal Systems
- State Complexity of the Multiples of the Thue-Morse Set
- A Decision Problem for Ultimately Periodic Sets in Non-standard Numeration Systems
- Numeration Systems: a Link between Number Theory and Formal Language Theory
- Separating Words from Every Start State with Horner Automata
- Magic numbers in periodic sequences