Dehn algorithm and normal forms in small cancellation groups I found this statement in B. Cavallo, D. Kahrobaei's paper arXiv:1311.7117 
Secret Sharing using Non-Commutative Groups and the Shortlex Order, page 7.
"C′(1/6) continue to be an ideal platform for this protocol because 
reducing words to a minimal length has polynomial time complexity using a deterministic version of Dehn’s algorithm. In fact, it is the same algorithm used to solve the word problem. "
Could someone provide a reference that Dehn algorithm reduces words to normal forms in C'(1/6) groups in polynomial time? If this is not true, then in which classes of groups except virtually free gps is this true? 
Thanks,
Olga
 A: Gilman, Hermiller, Holt and Rees proved that only virtually free groups have length-reducing rewriting systems that take any word to a geodesic word so if by normal form, you mean geodesic then you are quite right that only virtually free groups will do.  I will look for the published reference.  I have an old preprint.
Added.  Here is the link
Added.  In Billington, Holt and Epstein, here, it is shown that the shortlex normal form of an element of a hyperbolic group can be computed in linear time. However, the automatic structure is considered precomputed.  For hyperbolic groups in general, this can be painful to compute but I don't know about small cancellation groups.
A: The proof is not difficult, and the argument can be found in older publications if you hunt around. I think it is essentially proved in a paper by Otto and Madlener.
The point is that, if there is a Dehn algorithm that reduces a word to a geodesic, then you can cary out the reduction on a single stack. So the word problem of the group as a formal language is context-free, and it follows by the Muller-Schupp Theorem that the group is context-free. (But of course the proof of that uses the deep result of Dunwoody about the accessibility of finitely presented groups.)
To see that you can do the reduction on a single stack, observe that if you have a geodesic reduction of the word read so far on the stack, then the next generator you read can reduce the geodesic length by at most one, and so you will have to do at most two length reductions with the Dehn algorithm to reduce the new word to a geodesic. Since that requires only a bounded amount of space, you can carry it out on the stack.
