
Computing area in presentations of the trivial group
Timothy Riley Proc. Amer. Math. Soc. 145 (2017), 5059–5069 We give polynomialtime dynamicprogramming algorithms finding the areas of words in the presentations < a, b  a, b > and < a, b  a^k, b^k; k \in N > 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 RNAfolding. In the second, area is what Jiang called width and studied when counting fixed points for selfmaps 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.
