automatons over 1-symbol alphabet

[Roland Bacher]

Nice problem!

A related question:

what is known in the symmetric case (maximal number of
distinct subsets S(0)=*, S(1),S(2), where S(k) is the set
of vertices reachable in k steps starting at a given
initial vertex * in a symmetric graph with n vertices)? 

By the way, this problem is closely related to correspondence algebras
on finite sets:

Consider n times n matrices with all entries >= 0. Call the set
of strictly >0 entries the support supp(A) of such a matrix A.
It is obvious that supp(AB) of the matrix product AB of two such
matrices depends only on supp(A) and supp(B). We get thus a 
product-law on all 2^(n^2) possible supports which is 
(easily seen to be) associative.

This yields a semi-group CS(n) whose semi-group algebra is the
correspondence algebra on n elements. 

I call this semi-group the "correspondence semi-group"
(I ignore if it has already a perhaps different name!)

The above question asks for the maximal number N=N(A) (for 
A a positive matrix as above, representing an element of the
semi-group CS(n)) such that the supports

supp(J),supp(AJ),supp(A^2J),...,supp(A^(N-1)J)

are all different where J is a positive non-zero (n times n) matrix
whose support contains only entries in the first row.

Related problems:

- Consider only matrices with symmetric support (my question above).

- Count the maximal possible number of different supports
supp(A),supp(A^2),supp(A^3),... for A in CS(n). (One might call 
this the "maximal order" of a cyclic semigroup in the 
correspondence semi-group CS(n)).

- Same question for semi-groups generated by 2,3,4,.. elements in CS(n).

- Number of minimal generators necessary for generating the entire
semi-group CS(n).

- One might also ask some of these questions for elements in 
the semi-group algebra (whose elements are linear combinations 
of supports, addition is the obvious one by adding coefficients 
corresponding to identical supports, multiplication is by 
extending the semi-group product linearly).


I have however no idea (and unfortunately also no time)
for attacking these problems. 

Best whishes,   Roland Bacher
 



On Tue, Jan 10, 2006 at 04:44:18AM -0800, Max wrote:
> Hello!
> 
> I would like to bring to your attention the following sequence.
> 
> Let a(n) be the maximum number of states of the minimum deterministic 
> automaton that is equivalent to a nondeterministic automaton with n states 
> over 1-symbol alphabet.
> 
> Alternative definition:
> 
> Suppose that we have a labyrinth consisting of n rooms and one-way 
> corridors connecting some of them (two rooms A and B may be connected by 
> two corridors A->B and B->A). One room is called starting.
> Let R(k) be a set of all rooms that can be reached from the starting room 
> after passing through exactly k corridors. We need to construct a labyrinth 
> with the maximum number of distinct R(k), i.e., a set { R(0), R(1), R(2), 
> ... } (that is actually a finite set) must be of the largest possible size. 
> This size is a(n).
> 
> This problem was proposed by Sergey Podzorov in russian math forum 
> http://www.nsu.ru/phorum/read.php?f=29&i=5505&t=5505
> 
> By direct enumeration I've shown that a(n)=(n-1)^2+2 for n=1..6. A 
> labyrinth giving rise to this number looks like
> 
> v----------|
> 1->2->...->n
> ...^_______|
> 
> where 1,2,...,n are rooms with the starting room 1 and the arrows are 
> corridors.
> 
> For example, for n=3 this labyrinth gives
> R(0) = { 1 }
> R(1) = { 2 }
> R(2) = { 3 }
> R(3) = { 1, 2 }
> R(4) = { 2, 3 }
> R(5) = { 1, 2, 3 }
> R(6) = { 1, 2, 3 }
> ...
> implying a(3)=6.
> 
> 
> Rustem Aidagulov claims that the formula a(n)=(n-1)^2+2 holds for all n<20, 
> n=22, and n=23 but nobody has verified his claim yet.
> 
> For larger n, the number (n-1)^2+2 is not the best possible.
> For example, for n=29 there is a labyrinth of the following shape. There 
> are five directed corridors from the starting room to five other rooms that 
> belong to disjoint directed cycles of length 2,3,5,7,11 respectively. This 
> labyrinth gives 1+2*3*5*7*11=2311 distinct R(k)'s and 2311>=(29-1)^2+2=786.
> 
> It makes sense to add the sequence a(n) to OEIS but all known values 
> coincide with the sequence (n-1)^2+2=A059100(n-1).
> What should we do in this case?
> 
> Your help in extending and/or analyzing this sequence will be appreciated.
> 
> Max
>