Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

Computing area in presentations of the trivial group


Author: Timothy Riley
Journal: Proc. Amer. Math. Soc. 145 (2017), 5059-5069
MSC (2010): Primary 20F05, 20F10, 68W32
DOI: https://doi.org/10.1090/proc/13625
Published electronically: August 29, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We give polynomial-time dynamic-programming algorithms finding the areas of words in the presentations $ \langle a, b \mid a, b \rangle $ and $ \langle a, b \mid a^k, b^k; \ k \in \mathbb{N}\rangle $ of the trivial group.

In the first of these two cases, area was studied under the name spelling length by Majumdar, Robbins and Zyskin in the context of the design of liquid crystals. We explain how the problem of calculating it can be reinterpreted in terms of RNA-folding. In the second, area is what Jiang called width and studied when counting fixed points for self-maps of a compact surface, considered up to homotopy. In 1991 Grigorchuk and Kurchanov gave an algorithm computing width and asked whether it could be improved to polynomial-time. We answer this affirmatively.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 20F05, 20F10, 68W32

Retrieve articles in all journals with MSC (2010): 20F05, 20F10, 68W32


Additional Information

Timothy Riley
Affiliation: Department of Mathematics, 310 Malott Hall, Cornell University, Ithaca, New York 14853
Email: tim.riley@math.cornell.edu

DOI: https://doi.org/10.1090/proc/13625
Keywords: Exact area, group presentation, width, RNA-folding
Received by editor(s): November 1, 2016
Received by editor(s) in revised form: December 15, 2016
Published electronically: August 29, 2017
Communicated by: David Futer
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society