My research interests are on the boundary of abstract algebra and
theoretical computer science. Broadly speaking, I am interested in
finding ways that computer science can be brought to bear on open
problems from abstract algebra. In particular, I am interested in
the following areas:
-
Algorithms for studying infinite groups.
In theoretical computer science, we classify problems according
to how difficult it is to solve them on a computer:
does there exist an algorithm to solve the problem
which terminates in a finite amount of time?
If so, how long does it take? How much memory is needed?
Most of my work in this area has focused on problems that arise
in the study of infinite solvable groups.
In this context
most of the classical questions are computationally
very difficult; therefore,
the development of practical algorithms
has required new theoretical
insights into the structure of such groups.
-
Applications of formal language theory
to the study of infinite groups.
Several languages are associated with an infinite groups
(when the group is
given by what is known as a "finite presentation").
The most famous of these is the word problem ,
i.e. the set of those strings, or words, that represent the
identity element of the group.
It is natural to ask: if we are able to classify
the word problem of a given group
(using the hierarchy of languages from
formal language theory), what does this tell us about the group?
Refereed Journal Publications
-
Baumslag, G., Miller, C.F. M., Ostheimer, G., "Recognizing decompositions in finitely generated torsion-free nilpotent groups". International Journal of Algebra and Computation 26 (2016), 1529-1546.
-
Elder, M., Elston, G., Ostheimer, G., "On groups that have normal forms
computable in logspace", Journal of Algebra 381 (2013), 260-281.
download pdf
;
-
Baumlsag, G., Miller, C. F. M., Ostheimer, G., "Subgroups of free metabelian groups", Groups, Geometry and Dynamics 4 (2010), 657-679.
download pdf
;
-
Elder, M., Kambites, M., Ostheimer, G., "On groups and counter automata", International Journal of Algebra and Computation 18 (2008), 1345-1364.
download pdf
;
-
Elston, G. and Ostheimer, G.,
``On groups whose word problem is solved by a counter automaton'',
Theoretical Computer Science
28 (2004), 175-185.
download pdf
;
-
Eick, B. and Ostheimer, G.,
``On the orbit-stabilizer problem for integral matrix
actions of polycyclic groups'',
Mathematics of Computation
72 (2003), 1511-1529.
download ps
-
Ostheimer, G.,
``Practical algorithms for polycyclic matrix groups'',
Journal of Symbolic Computation
28 (1999), 361-379.
download ps
-
Lo, Eddie H. and Ostheimer, G.,
``A practical algorithm for finding matrix
representations for polycyclic groups'',
Journal of Symbolic Computation
28 (1999), 339-360.
download ps
-
Fredman, M. L., Johnson, D. S., McGeoch, L. A., and Ostheimer, G.,
``Data structures for traveling salesmen'',
Journal of Algorithms
18 (1995), 432-479.
Refereed Conference Proceedings
-
Ostheimer, G.,
``Algorithms for polycyclic-by-finite matrix groups'',
Groups and Computation II, ACM (1997), 297-307.
-
Fredman, M. L., Johnson, D. S., McGeoch, L. A., and Ostheimer, G.,
``Data structures for traveling salesmen'',
Proceedings 4th Annual ACM-SIAM Symposium on Discrete Algorithms (1993),
145-154.