Computational experiments in braids.

Title: Computational experiments in braids.
Identifier: AAI9820516
identifier: 9820516
Creator: Brenner, Mike.
Contributor: Adviser: Michael Anshel
Date: 1997
Language: English
Publisher: City University of New York.
Subject: Computer Science | Mathematics
Abstract: Computational experiments were conducted on a class of problems in braid group theory. Using various data structures, certain braid group algorithms were implemented, forming a braid group laboratory. During the course of the experiments, the impact of the various data structures was assessed and used to analyze and improve the performance of the algorithms on braid groups and on other groups. The effects of cohesion and coupling within braids were examined to relate the complexity of a braid to other forms of complexity. Examples and counterexamples were developed for the complexity of the algorithms needed to work with certain braids. One of the braid algorithms that developed from these experiments is a braid word problem eliminator (as opposed to a reducer) which approaches being a braid word problem solver. The states and patterns of this algorithm require space that is linear in the number of crossings. The worst case time is cubic in the length of the braid and linear in the number of strands. This is not as fast as the quadratic time in which the braid word problem is known to be solvable.
Type: dissertation
Source: PQT Legacy CUNY.xlsx
degree: Ph.D.