It is well known that the set of all natural numbers divisible by a fixed modulus can be recognized by a finite state machine, assuming that the numbers are written in standard base- representation. It is much harder to determine the state complexity of the minimal recognizer [1]. In this article we discuss the size of minimal recognizers for a variety of numeration systems, including reverse base- representation and the Fibonacci system.

Automaticity and State Complexity

Automaticity

A sequence is -automatic if it can be recognized by a finite state machine in the sense that, on input , the machine outputs . Here is usually written in standard base- notation, though other numeration systems are also considered. A typical example is the Morse-Thue sequence , which is often defined in terms of iterated morphisms. However, there is an alternative characterization that shows that is the digit-sum of the binary expansion of modulo 2. Thus, the Morse-Thue sequence is 2-automatic. The study of automaticity has lately attracted a lot of attention; see the excellent book by Allouche and Shallit [2].

Little is known about the state complexity of the finite state machines in question: given an automatic sequence, what is the size of the smallest machine that recognizes it? Often there is a canonical machine that witnesses the automaticity of a sequence and provides an upper bound on , but the inherent complexity of the minimization process often makes it very difficult to pin down the exact state complexity of the sequence. Using a suitable computational environment, it is possible to generate sample data that can lead to plausible conjectures. More computation can then help to prune false assumptions and produce answers, at least in a few selected cases. This is particularly important since the combinatorics of our problem are fairly complicated, so that, in general, no simple closed-form solutions are available.

Most of the computations in this article depend on Automata, a large package that implements finite state machines (see [3] for a description of a version of the package). The package is freely available at www.cs.cmu.edu/~sutner and contains installation instructions.

Divisibility and Horner Automata

In this article we study the state complexity of machines recognizing the set of all multiples of a fixed modulus . It is not hard to see that is indeed -recognizable for any base (we will focus on the interesting case in what follows). We denote the digit alphabet by . There is a canonical deterministic finite automaton (DFA) that accepts all strings that denote numbers in base- notation that are divisible by . The state set of is the set of modular numbers and the right action is given by

If we fix the initial state to , we have for any word . Here denotes the value of : the value of word is

Thus, the action corresponds to the standard Horner scheme of evaluating polynomials and we refer to these machines as Horner automata. Here are some sample Horner automata.

We generate all words in the acceptance language of length 6 and compute their numerical values.

As required, the remainders are all 0. Other useful information about the associated language can be extracted from the automaton. For example, we can obtain a generating function for the growth rate.

Here is a different base and modulus.

Horner automata provide an upper bound for the state complexity of divisibility: , regardless of the base . Alas, the bound is usually far from tight.

Minimal Divisibility Recognizers

Pinning Down Behavioral Equivalence

Though the canonical Horner DFAs fail to be minimal, in general they are still helpful in determining the structure of the minimal recognizers. Recall that any DFA for a regular language covers the minimal DFA, so we need to determine the fibers of the covering map. Abstractly, we can describe the corresponding partition as follows. Let

It is well known that for radix representation, automaticity of divisibility follows from the fact that the following equivalence relation has a finite index when :

[4]. The index of this equivalence relation is none other than the state complexity we are interested in.

However, this characterization does not readily produce a reasonable description of the state complexity.

By applying a standard minimization algorithm to our Horner automata we can generate some data that will guide the search for a description of the state complexity. In the following table is the row index and is the column index.

We write for the size of the minimal DFA that recognizes numbers divisible by in base- notation. If we disregard , the table suggests that . Moreover, for and coprime we have , so that the Horner automaton is already minimal. Both observations are easy to prove.

For the remaining cases, note that for any word we have in :

The behavior of state in is therefore

Define the witness for to be the length-lex minimal word in the behavior of .

Suppose has a witness of length . Then is a solution of the linear equation

(1)

where the additive coefficient is bounded as . Thus, in order to determine equivalence of states, we have to characterize the solution sets of this equation. Let

and

We will refer to these solution sets as cumulative versus strict. Note that . Since the length of the behavioral witness matters, rather than just the associated numerical value , we have to consider the strict rather than just the cumulative solution sets. Our goal is to determine the number of solution sets and the levels at which they appear. As it turns out, the combinatorics are somewhat complicated so that the easy availability of sample data is crucial.

Examples

Here are some examples of solution sets. We use a little wrapper function SolveModEq to solve modular equations in a useful format. The strict version removes solutions from lower levels. For coprime modulus and base all solution sets have size one; all parameters are feasible in the sense that equation (1) has a solution at some level .

Here modulus and base are not coprime. The size of the solution sets reaches a plateau at level .

Note that the solution sets are of the form for We refer to as the stride of the solution set. In the example, .

Here the size of the solution sets increases until all of appears as a solution somewhere.

Here are the same examples with strict solutions. The coprime case is trivial, so we skip it.

Note how the size of some of the strict solutions sets deviates from .

Counting Cumulative Solutions

Let us tacitly assume that parameter is feasible; that is, , in which case the cardinality of is ; the empty solution set is dealt with separately. There are two natural parameters that are important for the description of all solution sets. First, the depth of and is the least level for which . Second, the saturation value is the least such that . Note that

Letting , at level , there are solution sets of size each. Within each solution set the elements satisfy .

We leave the proof as an exercise.

Examples

We can get a short overview of the structure of the solution hierarchy with the command ProfilemB. The command prints out the key parameters, the stride of the solution sets, the number of solution sets, and the size of the solution sets. Here is a case where .

Here is a sanity check.

And here is .

Counting Strict Solutions

Let be the least such that , and let , the rank of and , be the maximum such that for some . It is easy to see that if is a power of we have , and otherwise; hence, it suffices to consider levels . Up to level the solution sets grow exponentially in size, so for all feasible coefficients, and there are solution sets at level .

However, for we have to contend with potentially empty solution sets. Recall that . Whenever , the number of feasible coefficients at level is rather than .

B. Alexeev [1] has found a way to avoid following the hierarchy of solution sets all the way to the end, at least in some cases. Let be the least such that . Note that , and it may well happen that .

For a proof see [1].

Reverse Base B

Brute Force

For reverse base- notation, the construction of the minimal DFA that accepts all strings that denote numbers divisible by is somewhat more complicated. One possible choice of a canonical, though not necessarily minimal, DFA is to use as the state set a Cartesian product , where is the multiplicative submonoid of generated by . The right action is given by

the initial state is , and the final states are of the form . Thus, the first component maintains the numerical value of the input string, modulo , and the second provides the appropriate multiplier for the next digit.

Note that the size of this automaton is a multiple of and may be close to . When is prime and is a generator of the multiplicative subgroup , the machine will have states.

However, the minimal DFA here is much smaller.

Some more computation suggests that indeed the size of the minimal automaton here is bounded by .

The Canonical Nondeterministic Automaton

We write for the size of the minimal DFA that recognizes numbers divisible by in reverse base- notation. Since the deterministic machine from the previous section appears to be overly large, it is tempting to consider a nondeterministic one in an effort to determine : the reversal of the canonical DFA for standard base . This machine has size and the transitions again are determined by linear equations modulo . Recall that in the transitions given by . Hence we have in :

(2)

Thus, the reachable states in the full power automaton of are going to be the solution sets of where . Note that this time we are dealing with cumulative solutions, not the strict hierarchy from the first section.

The command DivisibilityDFA with option preserves the structure of the state set:

This state set is none other than the solution sets for equation (1). Since the function disregards the empty set as a possible solution set, we only get six states out of seven in the next computation.

When and are coprime, there is no sink since the equation has a solution for all choices of the coefficients.

Otherwise there are one or two trap states; in the latter case only one of the two is final.

Since we are not concerned with the strict hierarchy, it is actually a little easier to count the number of all solution sets in this case.

As before let be the least such that and let . Also let be the maximum such that some new solution appears at level . Thus, if is a power of , we have , and otherwise.

Minimal Recognizers

We claim that the power automaton obtained from is always reduced and thus already minimal. To see this, call a state in a machine rich if its behavior contains at least one word not in the behavior of . Clearly, any state in the power automaton of that contains a rich state cannot be equivalent to any other state. Hence it suffices to prove the following.

Fibonacci Base

Any strictly increasing sequence of positive integers where gives rise to a numeration system. In order to keep the number of distinct digits finite, the condition that be bounded is usually imposed [5]. In this case the digits can be chosen as where is the largest integer less than the supremum. In general, numbers will admit multiple representations in such a numeration system and the normalized representation can be defined as the one obtained by the natural greedy algorithm.

A classical example is given by the Fibonacci sequence (starting at the third term): In this case is the golden ratio, . Hence there are only digits and the normalized representation can be computed as follows. We need a little auxiliary function that returns the largest Fibonacci number not greater than a given number.

Then a standard greedy algorithm will produce the Fibonacci representation of a number.

A famous open problem related to the Fibonacci sequence is to determine the period length of the sequence modulo . These numbers are sometimes referred to as Pisano numbers; see Sloane’s database of sequences at A001175.

We write for the length of the sequence modulo . It is easy to see that the function is multiplicative. It seems that for primes we have but no proof is known. Moreover, the behavior of on primes is not well understood either. It is known that exactly when there is a primitive root modulo such that . Also, if and only if .

Brute Force

The obvious brute-force construction of a finite state machine for numbers in Fibonacci base (not necessarily normalized) that are divisible by is to use as the state set the Cartesian product , where is the Pisano number of . The right action on is given by

where denotes the Fibonacci number. It is straightforward to construct this automaton, assuming for the time being that is the initial and final state. The method employed is based on the construction of a cyclic semi-module, which is then interpreted as a DFA. Automata contains a command GenerateDFA that implements the necessary machinery.

At present, the automaton only accepts words with a length that is a multiple of .

In order to get words of arbitrary length we need to add more initial states.

A small sanity check: the numerical values are all multiples of 3—and all such values seem to appear.

A Canonical Automaton

The automaton MM from the previous section is nondeterministic because of its multiple initial states, though all transitions are deterministic. What is the size of the corresponding power automaton and minimal automaton?

The power automaton is already minimal and much smaller than might be expected. To see why, note that MM is a permutation automaton. Hence, the size of all the states in the power automaton is , the Pisano number of , and the number of initial states. In fact, all these states contain exactly one element for each .

But then we might as well use sequences of length of remainders modulo as states. The action on these sequences can be chosen to be

where is a period of the Fibonacci sequence modulo , and indicates a cyclic shift to the left. It is straightforward to implement this automaton, using again the command GenerateDFA from Automata.

While the states of these automata depend on the Pisano numbers, the size of the automata appears simply to be .

It is easy to establish this conjecture. The states are all Fibonacci-type sequences modulo but with different initial conditions. All initial conditions occur since the standard sequence has the form .

It follows that the minimal automaton can have size at most . To show that this bound is tight, it suffices to prove that the canonical automaton is already reduced. To this end, write for the input , so that . Letting , is final if and only if . Hence, all states have distinct behavior, and we are done.

References

[1]	B. Alexeev, “Minimal DFAs for Testing Divisibility,” Journal of Computer and System Sciences, 69(2), 2004 pp. 235-243. DOI Link: doi:10.1016/j.jcss.2004.02.001.
[2]	J-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge: Cambridge University Press, 2003.
[3]	K. Sutner, “Automata: A Hybrid System for Computational Automata Theory,” in Proceedings of the Seventh International Conference on Implementation and Application of Automation (CIAA‘02), Tours, France (J-M. Champarnaud and D. Maurel, eds.), Berlin: Springer, 2002 pp. 221-227.
[4]	V. Bruyère, G. Hansel, C. Michaux, and R. Villmaire, “Logic and p-Recognizable Sets of Integers,” Bulletin of the Belgian Mathematical Society, 1, 1994 pp. 191-238.
[5]	V. Bruyère and G. Hansel, “Recognizable Sets of Numbers in Nonstandard Bases,” in Proceedings of the Second Latin American Symposium on Theoretical Informatics, Valparaiso, Chile (R. A. Baeza-Yates, E. Goles, and P. V. Poblete, eds.), Lecture Notes in Computer Science, 911, London: Springer-Verlag, 1995 pp. 167-197.
Klaus Sutner, “Divisibility and State Complexity,” The Mathematica Journal, 2010. dx.doi.org/doi:10.3888/tmj.11.3-8.

About the Author

Klaus Sutner teaches computer science and internal martial arts at Carnegie Mellon University. His research interests lie in the area of computability, in particular, computations involving finite state machines and related systems such as cellular automata. Over the years, the Automata package used in this article has proven to be a great asset in research in automata theory and in teaching this beautiful subject to students.

Klaus Sutner
Carnegie Mellon University
5000 Forbes Avenue
Pittsburgh, PA 15213
sutner@cs.cmu.edu