The mechanical discovery of certain problem symmetries

摘要

This paper presents several methods for analysing finite state problems to discover certain types of symmetry. The methods are based on techniques used in Sequential Machine Theory, especially the use of partitions that have the Substitution Property. Amarel's investigations of a type of time-reverse symmetry have also been extended to a wider class of problems. All the symmetries discussed enable substantial savings in search effort to be obtained by effectively reducing the size of the search space.