Group-Theoretic Tools and Applications

本研究的主要主题是将群论技术应用于各种各样的搜索问题。最终目标是将代数技术与标准搜索方法结合起来，以解决目前两种方法都无法单独解决的“难题”。这需要三个主要研究工作的相互作用：研究执行基本群计算的有效算法；开发一个实验系统，用于在顺序和并行机器上测试算法思想；探索在代数环境中表示搜索问题的方法和解决这些问题的工具。所要研究的算法在群计算的一般算法的发展以及群论在现实世界问题中的应用中起着基础作用。应用范围从组合对象的同构测试到运筹学中的运输问题。算法和应用程序将在传统的顺序环境中实现，以支持各种数据结构和技术的实验，并且在适当的情况下，在大规模并行SIMD机器上实现。

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.