Geometric and combinatorial group theory, including
algorithmic properties
(rewriting systems, automaticity, almost convexity, etc.),
asymptotic properties (growth functions,
isoperimetric/diametric/tame filling
functions), and homological properties (finiteness conditions,
finite derivation type).
Non-commutative and commutative Groebner bases (i.e. rewriting systems for
algebras).
Description:
Group theory is the study of symmetries of objects.
The "word problem", originally stated by M. Dehn in 1911,
asks if there is an algorithm
which can determine whether or not
performing a sequence of rigid
motions of an object (for examples, reflections
and rotations) results in returning the object
to its original position.
Solvability of the word problem and related
algorithmic problems is of central interest
in geometric group theory. For the cases in which
a problem is solvable, it is also important to understand
the complexity of the possible solutions.
Computer science tools from formal language
theory are often valuable in this complexity analysis.
The goal of much of my research
is two-fold, both to find large classes of groups for
which algorithmic problems have particularly
tractable solutions, and to understand what algebraic,
asymptotic, geometric, or topological
properties of a group are implied by such algorithms.