8
$\begingroup$

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

Improve this question
$\endgroup$
1
  • $\begingroup$ It has actually been corrected now in the paper. $\endgroup$
    – user64160
    Commented Dec 19, 2014 at 21:26

2 Answers 2

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ What is meant by deterministic variation is ambiguous but applying a finite set of length reducing rules is excluded by the above paper. $\endgroup$
    – Benjamin Steinberg
    Commented Dec 2, 2014 at 18:55
  • $\begingroup$ Note that Hermiller was also an author of the linked paper. $\endgroup$
    – Derek Holt
    Commented Dec 3, 2014 at 7:19
  • $\begingroup$ Derek, will fix it. $\endgroup$
    – Benjamin Steinberg
    Commented Dec 3, 2014 at 11:51
5
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ is this the paper where they look at which groups have a finite confluent rewriting system that turns any word into a geodesic? They had a conjecture that I started to look at years ago with A. Weiss and this is why I remembered your paper with Gilman and Rees. $\endgroup$
    – Benjamin Steinberg
    Commented Dec 2, 2014 at 23:14
  • $\begingroup$ I think so. I can find the paper in question at some stage, but I travelling around at the moment, so I won't be able to do that this week. I just remember finding the identical argument in one of their papers and thinking that we should have cited it! $\endgroup$
    – Derek Holt
    Commented Dec 2, 2014 at 23:46
  • $\begingroup$ Presumably the conjecture you mention is that a group has a finite confluent length reducing rewriting system if and only if it is a free product of f.g. free groups and finite groups? $\endgroup$
    – Derek Holt
    Commented Dec 3, 2014 at 7:30
  • $\begingroup$ Yes, Derek. That one. $\endgroup$
    – Benjamin Steinberg
    Commented Dec 3, 2014 at 11:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .