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
-- Regards, Vladimir
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk