Re: [boost] Re: Experiment in Automata syntax

From: Vladimir Prus (ghost_at_[hidden])
Date: 2001-06-27 02:54:52

On Tuesday 26 June 2001 21:11, Jeremy Siek wrote:	
> On Tue, 26 Jun 2001, Vladimir Prus wrote:
> ghost> 3.  Algorithms.
> ghost> Should be more of them. E.g. I would like to see Hopcroft's
> minimization ghost> algorithm and isomorphism algorithm. Fortunately, new
> algorithm can be ghost> plugged as they are written, so this issue is not
> very important.
>
> BGL has an isomorphism algorithm. The algorithm used is not the best, but
> it is good for many situations. The best algorithm is the one used by the
> "nauty" implementation, and is quite complex. I've made a stab at
> converting this algorithm, but ran out of time.

I may be wrong, but I think that automata isomorphism can be implemented much 
more efficiently than graph isomorphism. The fact that edges are maked with 
transition symbols considerably decreases degree of freedom -- once 
correspondence between two vertices is established (e.g. between initial 
states) there's but one possible correspondence between successors. 
Therefore, two "parallel" dfs are sufficient to find if automata are 
isomorphic.

-- 
Regards,
Vladimir