@spacehobo I'm afraid I didn't find the clusters by any automated procedure. I found them by knowing something about how I'd generated those graphs in the first place. I don't know of any software that would look for clusters of that kind automatically. It's an interesting thought, though!In the first of my graphs here, the clusters are equivalence classes under two types of symmetry. The input to the state machine represents a pair of strings zipped together, symbolically describing adjacent tiles in a tiling (or rather, the machine tests _whether_ they could be adjacent). So the machine ought to be symmetric in swapping the two input strings. Also the symbols A,B,U,V represent the triangles you get by dividing Penrose kite and dart tiles in half along their line of symmetry, so there's a second symmetry in exchanging A↔B and U↔V. That gives natural groups of four vertices, except when things are fixed points of one or other transformation, or the two symmetries coincide.In the second graph, there's only one input string, so I lost one of those symmetries – you can still exchange A↔B and U↔V, but you can't swap the inputs any more. But the second graph is the determinisation of the first, so each state corresponds to a set of states of the original graph, and I clustered states corresponding to the same set.
undefined
Social Forum federato con il resto del mondo. Non contano le istanze, contano le persone
