On 06/23/2011 12:52 PM, Evan Driscoll wrote:
I'm still struggling with the edge label restrictions as well. The only way I can think of to incorporate them is to make sure that the set of labels from corresponding nodes is the same: but that's insufficient:
A B (q0) ---------> ((q1)) (p0) ------------> ((p1)) | | | B | A | | V V (q2) (p2)
These automata are not isomorphic; they don't even have the same language. But if you can only look at each vertex and the edges that are incident on it, it looks like it is.
Actually I lied; you can tell in that case, since q1 <--> p1 by the isomorphism, but the edges incident on q1 is just A and those incident on p1 is just B. But this works to illustrate my point: A B (q0) ---------> ((q1)) (p0) ------------> ((p1)) | /\ | /\ | B | | A | | | B | | A V | V | (q2) (q3) (p2) (p4) /\ /\ | | | A | B | | (q4) (p3) q0, p0 both have no incoming and one A and one B outgoing q1, p1 both have one A and one B incoming and no outgoing q2, p2 both have one A and one B incoming and no outgoing q3, p3 both have one B outgoing and no incoming q4, p4 both have one A outgoing and no incoming Evan