Recognition of topological equivalence of patterns by array automata

摘要

The complexity of array automata which compute Beyer's topological matching predicate is studied. This predicate on two n × n figures is true if and only if the trees describing their topological structure are isomorphic. An algorithm is proposed which is proved to operate in order of n2 steps on pairs of n × n figures, a significant improvement over Beyer's order of n4 algorithm.