Efficient Average-Case Algorithms for the Modular Group

  • Jin-Yi Cai ,
  • Wolfgang Fuchs ,
  • Dexter Kozen ,
  • Zicheng Liu

Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on |

Published by IEEE

Publication

Download BibTex
The modular group occupies a central position in many branches of mathematical sciences. In this paper we give average polynomial-time algorithms for the unbounded and bounded membership problems for finitely generated subgroups of the modular group. The latter result affirms a conjecture of Y. Gurevich (1990).