Pattern recognition and the Whitehead minimization problem.
Item
-
Title
-
Pattern recognition and the Whitehead minimization problem.
-
Identifier
-
AAI3169953
-
identifier
-
3169953
-
Creator
-
Miasnikov, Alexei D.
-
Contributor
-
Adviser: Robert Haralick
-
Date
-
2005
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Computer Science
-
Abstract
-
In this research we show that the ideas of experimental mathematics and, in particular, application methods of statistical pattern recognition can be of great use in group theory.;We apply exploratory data analysis to the Whitehead Minimization Problem, which concerns itself with the problem of finding elements of the minimal length in the automorphic orbit of an element in a free group. The only known algorithm, which is due to Whitehead, has exponential dependence on the rank of a free group. Moreover, the worst case is inevitable except for some trivial cases.;We begin by describing a stochastic search procedure which surprisingly performs much better then the classical procedure. We perform statistical analysis of the solutions produced by the stochastic procedure and the non-minimal elements themselves to obtain a number of non-trivial search heuristics which allow one to predict the length-reducing automorphisms for a particular non-minimal element.;The worst case behavior of the Whitehead's procedure occurs when it is applied to a minimal element. We present a probabilistic classification system based on nonlinear regression and Support Vector Machines which recognizes minimal elements with the rate of misclassification error being less then 1%.;Based on the methods described above we develop fast deterministic algorithm which significantly outperforms the original one and is able to avoid the exponential blowout on most inputs. In addition we present a probabilistic algorithm which is very robust and can be used in groups with large ranks, where any other known algorithm fails to produce.;Another important contribution of this thesis is the formulation of a number of rigorous mathematical conjectures dealing with the structure of the problem and its generic behavior (behavior on most inputs). In particular, based on statistically significant evidence we conjecture that most non-minimal elements in a free group are reducible by one of the Nielsen automorphisms which can be identified by inspecting the structure of the corresponding Whitehead Graph and that the feature vectors of minimal elements are located in a "compact" region in the corresponding space and can be bounded by a hypersurface.
-
Type
-
dissertation
-
Source
-
PQT Legacy CUNY.xlsx
-
degree
-
Ph.D.
