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
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?)

  • [BGSW16] K. Bringmann, F. Grandoni, B. Saha, and V. Williams, Truly sub-cubic algorithms for language edit distance and RNA folding via fast bounded-difference min-plus product, In FOCS (2016).
  • [BRS07] Noel Brady, Tim Riley, and Hamish Short, The geometry of the word problem for finitely generated groups, Advanced Courses in Mathematics. CRM Barcelona, Birkhäuser Verlag, Basel, 2007. Papers from the Advanced Course held in Barcelona, July 5-15, 2005. MR 2281936
  • [GK91] R. I. Grigorchuk and P. F. Kurchanov, On the width of elements in free groups, Ukrain. Mat. Zh. 43 (1991), no. 7-8, 911-918 (Russian, with Ukrainian summary); English transl., Ukrainian Math. J. 43 (1991), no. 7-8, 850-856 (1992). MR 1148843,
  • [Iva16] S. Ivanov., The bounded and precise word problems for presentation of groups, Preprint, 2016. arXiv:1606.08036.
  • [Jia89] Bo Ju Jiang, Surface maps and braid equations. I, Differential geometry and topology (Tianjin, 1986-87) Lecture Notes in Math., vol. 1369, Springer, Berlin, 1989, pp. 125-141. MR 1001182,
  • [Kao08] M.-Y. Kao, editor.
    Encyclopedia of Algorithms.
    Springer, 2008.
  • [Kar72] Richard M. Karp, Reducibility among combinatorial problems, Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972) Plenum, New York, 1972, pp. 85-103. MR 0378476
  • [KX] K. Koiliaris and C. Xu, A faster pseudopolynomial time algorithm for subset sum, To appear in SODA 2017. arXiv:1507.02318.
  • [MRZ09] Apala Majumdar, J. M. Robbins, and Maxim Zyskin, Tangent unit-vector fields: nonabelian homotopy invariants and the Dirichlet energy, C. R. Math. Acad. Sci. Paris 347 (2009), no. 19-20, 1159-1164 (English, with English and French summaries). MR 2566995,
  • [MRZ10] A. Majumdar, J. M. Robbins, and M. Zyskin, Tangent unit-vector fields: nonabelian homotopy invariants and the Dirichlet energy, Acta Math. Sci. Ser. B Engl. Ed. 30 (2010), no. 5, 1357-1399. MR 2778607,
  • [NB80] R. Nussinov and A. B.Jacobson, Fast algorithm for predicting the secondary structure of single-stranded rna, Proceedings of the National Academy of Sciences of the United States of America (1980), 77(11):6309-6313.

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

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