FSM union,intersection,factoring

From: V.Z.Nuri (vznuri_at_yahoo.com)
Date: 05/14/04 

Date: 13 May 2004 21:29:21 -0700

hi all, two questions on finite state machines (FSMs)

a.

about a decade ago I discovered a n^2 algorithm to
compute A/\B and A\/B (intersection, union) for epsilon free FSMs.
its quite simple, just doing
a simultaneous traversal of both graphs, so I presume
its in the literature somewhere. however, I have not
heard of it anywhere. does anyone know? (my own favorite
ref, hopcroft/ullman, define A/\B and A\/B in terms
of epsilon transitions, which can be removed with another
algorithm. but maybe the combination of their two algorithms
is the same as the n^2 dual-traversal algorithm.)

b.

given C and C=A/\B or C=A\/B, find suitable A,B. ie
"factor" the FSM C into a union or intersection of two
other FSMs A,B. I have not been able to find a discussion or
reference to this problem in the literature. esp seeking software
although it seems unlikely. I have the
nagging suspicion that group theory would be quite relevant,
but dont know the specifics. I know that there is an infinite
set of FSMs A,B but presumably there is in some sense
"canonical" factors.

PS I am aware of the excellent AT&T library for FSMs. it does
not have a factoring operation.