INVESTIGATIONS OF BRAID GROUP ALGORITHMS (COMPUTER SCIENCE, LOG-SPACE, COMPLEXITY, GARSIDE, ARTIN).
Item
-
Title
-
INVESTIGATIONS OF BRAID GROUP ALGORITHMS (COMPUTER SCIENCE, LOG-SPACE, COMPLEXITY, GARSIDE, ARTIN).
-
Identifier
-
AAI8515647
-
identifier
-
8515647
-
Creator
-
NAJARIAN, JOHN PANOS.
-
Contributor
-
Michael Anshel
-
Date
-
1985
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Computer Science
-
Abstract
-
The classical Artin algorithm for the word problem for braid groups is shown to have an exponential space and exponential time worst case. Monte Carlo experiments and enumerations show that the average case is non-linear (but appears to be a low order polynominal) for Artin's algorithm. Trends and patterns are analyzed.;Garside's algorithm for the word problem is then analyzed with respect to average and worst cases. Statistical evidence shows that the classical Garside algorithm has exponential space growth with respect to the number of braid strands. For braids with more than six strands, this algorithm easily exceeds the storage capacity of the present generation of mainframe computers. Many interesting properties are proven about the word diagrams of Garside's algorithm.;A variant of Garside's algorithm is proven to operate in non-deterministic linear space on a Turing Machine in the average and worst cases. In deterministic form, this algorithm requires at most quadratic space on a Turing Machine.;The Burau representation is used to construct other algorithms. A complexity-theoretic line of attack for the famous faithfulness conjecture of the Burau representation is demonstrated. The word problem for B(3) is proven to require logspace.;A variant of the Luginbuhl combing algorithm is designed for solving the word problem for braid groups. A brief analysis of it follows.;A new algorithm is designed for nearly solving the word problem for braid groups. This algorithm operates in log-space for all B(n) but it accepts some rare non-identity braids. Some counterexamples are shown.;The word problem for B(3) can be solved in linear time but with linear space usage.
-
Type
-
dissertation
-
Source
-
PQT Legacy CUNY.xlsx
-
degree
-
Ph.D.
-
Program
-
Engineering
