Group-Theoretic Tools and Applications

点击翻译按钮获取中文摘要

The principal theme of this research is the application of group-theoretic techniques to a wide variety of search problems. The ultimate objective is to combine algebraic techniques with standard search methods to solve "hard problems" which are currently solvable by neither method alone. This requires the interaction of three major research efforts: the study of efficient algorithms for performing fundamental group computations; the development of an experimental system for testing algorithmic ideas on both sequential and parallel machines; and the exploration of methods for representing search problems in an algebraic setting and tools for solving them. The algorithms to be studied play a fundamental role in the development of general algorithms for computing with groups as well as for application of group theory to real world problems. Applications are diverse and range from isomorphism testing of combinatorial objects to the transportation problems in operations research. Both algorithms and applications will be implemented in both a traditional sequential environment engineered to support experimentation with a variety of data structures and techniques, and, where suitable, on a massively parallel SIMD machine.