BORIS ALEXEEV

Title: BORIS ALEXEEV

Research Question: How many states does a minimal DFA that recognizes the set of base-b numbers divisible by k have?

Methodology: The author used two implementations of the Hopcroft minimization algorithm: a original Perl program and the highly-optimized AT&T FSM PackageTM. These algorithms were used to compute the function fb(k) for various values of b and k.

Results: The author derived a closed-form expression for the function fb(k) and used it to compute the number of states in the minimal DFA for various values of b and k. The function fb(k) exhibited some interesting patterns, such as the fact that the successive differences of fb(k) were the powers of 2 and 3, sorted in increasing order.

Implications: The results of this study have implications for the field of automata theory and could potentially lead to more efficient algorithms for recognizing the set of base-b numbers divisible by k. The interesting patterns observed in the function fb(k) also raise interesting questions about the nature of these patterns and whether they can be explained by any known mathematical principles.

Link to Article: https://arxiv.org/abs/0309052v1 Authors: arXiv ID: 0309052v1