|
Papers on Tarski
Problems Balanced presentations of the trivial
group on two generators and the Andrews-Curtis Using computers we described all trivial (perfect) groups given by balanced presentations of length at most 12. Then we proved (again using computers and genetic algorithms) that every balanced presentation on two generators of the trivial group satisfies the AC conjecture. 2. Whitehead method and Genetic Algorithms (with Alexei D. Miasnikov) Contemporary Mathematics, Contemporary Mathematics, v. 349, 2004, p. 89-114. We describe a genetic Whitehead's algorithm for finding minimal elements (elements of minimal length in automorphic orbits) in arbitrary free groups. The classical Whitehead's algorithm is extremely innefective for free groups of big ranks, but this genetic version of it works all right. Also we formulate several mathematical conjectures that came out of our experiments. 3. Pattern Recognition and Minimal Words in Free Groups of Rank 2 (with Robert M. Haralick and Alexei D. Miasnikov) Submitted. We describe a linear time probabilistic algorithm to recognize Whitehead minimal elements (elements of minimal length in their automorphic orbits) in free groups of rank 2. Moreover, for a non-minimal element the algorithm gives an automorphism that will most likely reduce the length of the element. This method is based on linear regression and pattern recognition techniques. I did not believe this myself first, untill I've seen it working with my own eyes. 4. Pattern Recognition Approaches to
Solving Combinatorial Problems in Free Groups (with Robert M. Haralick and Alexei D. Miasnikov), Contemporary Mathematics, v. 349, 2004, 1. In this survey paper we present some pattern recognition techniques that can be used in studying free groups. As an illustration we apply these methods to Whitehead minimization problem. Abstract to appear. |