We try to compare the complexity of deterministic, nondeterministic, probabilistic and ultrametric nite automata for the same language. We do not claim to have nal upper and lower bounds. Rather these results can be considered as experiments to nd advantages of one type of automata versus another type. Any deterministic nite automaton accepting the language has at least 2015 states. We started our research with a simple exercise: is there a nondeterministic nite automaton accepting the language and using much less states than 2015. The automaton that comes to our mind starts its work with one nondeterministic choice. In the rst case the automaton uses 5 states to accept the input word if its length is not a multiple of 5. In the second case the automaton uses 13 states to accept the input word if its length is not a multiple of 13. In the third case the automaton uses 31 states to accept the input word if its length is not a multiple of 31. Hence the automaton has 49 states. Unfortunately, this automaton accepts not the language L2015 but rather the language We add two new cycles. One of the cycles has 47 states but after the 46-th state there is another nondeterministic branching of the computation path. By Sylvester's theorem [5] this automaton accepts all input words whose length exceeds 45 46 1 = 2070 and the automaton has 49+47=96 states. However, it is possible to construct another nondeterministic automaton for the same language with 28 states only. This automaton starts its work with ? Supported by the project 271/2012 from the Latvian Council of Science. Partially supported by Latvian State Research programme NexIT project No.1.
one nondeterministic choice. In the rst case the automaton uses 2 states to accept the input word if its length is not a multiple of 2. In the second case the automaton uses 3 states to accept the input word if its length is not congruent to 2 modulo 3. In the third case the automaton uses 5 states to accept the input word if its length is not congruent to 0 modulo 5. In the fourth case the automaton uses 7 states to accept the input word if its length is not congruent to 6 modulo 7.In the third case the automaton uses 11 states to accept the input word if its length is not congruent to 11 modulo 11. Hence the automaton has 28+47= 75 states.
It much more di cult to prove that there is no smaller nondeterministic nite automaton accepting the language L2015. We used a computerized exhaustive search. Probably, it is a di cult problem to establish precise number of states s(N ) for nondeterministic nite automata accepting the languages
LN = f1n j n 6= N g: A more easy but still nontrivial problem is to establish asymptotical estimates for s(N ).
Theorem 1. The number of states s(N ) for nondeterministic nite automata accepting the language LN does not exceed O( l(ologgloNg)N2 ).
Proof. Following the traditional notation in number theory textbooks (e.g.
[
#(x) = p x log p x:
Hence the product F (t) = p1 p2 : : : pt is an exponent of t log t while the sum S(t) = r tpr equals t2 2 S(t) = (log t + log log t
+ o(1)) = O(
To construct an e cient probabilistic nite automaton for the language LN
we use distinct methods to process long and short input words. Of course, the
automaton cannot predict whether the current input word will be long or short.
If the input word is shorter than N 1 then we need to nd such a set of prime
modulos that most part of them show that the length of the input word di ers
from N . If the input word is longer then we need to construct a randomized
procedure rejecting all the words. To combine these (seemingly contradictory
goals) we use an idea proposed by R. Freivalds [
K. C pola et al.
Theorem 2. (R. Freivalds [
The method of the proof of Theorem 2 is used to ensure that all input words strictly shorter than N are rejected. In parallel, after reading arbitrary symbol from the input the probabilistic automaton goes to a special rejecting state with a probability 2 N . This ensures that if the length of the input word exceeds N 1 then the input word is rejected with probability at least 1 2 . Theorem 3. The number of states s(N ) for minimal probabilistic automata accepting the language LN with a probability 1 does not exceed O((log N )2log log N )2. nite 3
The notion of p-adic numbers widely used in mathematics but not so much
in Computer Science. R. Freivalds [
In mathematics, a stochastic matrix is a matrix used to describe the transitions of a Markov chain. A right stochastic matrix is a square matrix each of whose rows consists of nonnegative real numbers, with each row summing to 1. A stochastic vector is a vector whose elements consist of nonnegative real numbers which sum to 1. The nite probabilistic automaton is de ned as an extension of a non-deterministic nite automaton (Q; ; ; q0; F ), with the initial state q0 replaced by a stochastic vector giving the probability of the automaton being in a given initial state, and with stochastic matrices corresponding to each symbol in the input alphabet describing the state transition probabilities. It is important to note that if A is the stochastic matrix corresponding to the input symbol a and B is the stochastic matrix corresponding to the input symbol b, then the product AB describes the state transition probabilities when the automaton reads the input word ab. Additionally, the probabilistic automaton has a threshold being a real number between 0 and 1. If the probabilistic automaton has only one accepting state then the input word x is said to be accepted if after reading x the probability of the accepting state has a probability exceeding . If there are several accepting states, the word x is said to be accepted the total of probabilities of the accepting states exceeds .
Ultrametric automata are de ned exactly in the same way as probabilistic automata, only the parameters called probabilities of transition from one state to another one are real numbers between 0 and 1 in probabilistic automata, and they are p-adic numbers called amplitudes in the ultrametric automata. Formulas to calculate the amplitudes after one, two, three, steps of computation are exactly the same as the formulas to calculate the probabilities in the probabilistic automata. Following the example of nite quantum automata, we demand that the input word x is followed by a special end-marker. At the beginning of the work, the states of the automaton get initial amplitudes being p-adic numbers. When reading the current symbol of the input word, the automaton changes the amplitudes of all the states according to the transition matrix corresponding to this input symbol. When the automaton reads the end-marker, the measurement is performed, and the amplitudes of all the states are transformed into the pnorms of these amplitudes. The norms are rational numbers and it is possible to compare whether or not the norm exceeds the threshold . If total of the norms for all the accepting states of the automaton exceeds , we say that the automaton accepts the input word.
However, it is needed to note that if there is only one accepting state then the possible probabilities of acceptance are discrete values 0; p1; p 1; p2; p 2; p3; . Hence there is no natural counterpart of isolated cut-point or bounded error for ultrametric machines.
Theorem 4. For arbitrary odd prime p the number of states s(N ) for minimal p-ultrametric nite automata accepting the language LN with a probability 1 does not exceed O((log N )2log log N ).