A polynomial time algorithm for the conjugacy problem in Zn o Z

Autors/ores

  • Bren Cavallo CUNY Graduate Center, New York
  • Delaram Kahrobaei CUNY Graduate Center New York

Paraules clau:

Conjugacy problem, semidirect product, MSC (2010), Primary 20F10, Secondary 20E06.

Resum

In this paper we introduce a polynomial time algorithm that solves both the conjugacy decision and search problems in free abelian-by-innite cyclic groups where the input is elements in normal form. We do this by adapting the work of Bogopolski, Martino, Maslakova, and Ventura in [1] and Bogopolski, Martino, and Ventura in [2], to free abelian-by-innite cyclic groups, and in certain cases apply a polynomial time algorithm for the orbit problem over Zn by Kannan and Lipton [7].

Keywords: Conjugacy problem, semidirect product. MSC (2010): Primary 20F10, Secondary 20E06.

Biografia de l'autor/a

Bren Cavallo, CUNY Graduate Center, New York




Descàrregues

Com citar

Cavallo, B., & Kahrobaei, D. (2014). A polynomial time algorithm for the conjugacy problem in Zn o Z. Reports@SCM, 1(1), 55–60. Retrieved from https://revistes.iec.cat/index.php/reports/article/view/124908

Número

Vol. 1 Núm. 1 (2014)

Secció

Articles

Llicència

The intellectual property of articles belongs to the respective authors.
On submitting articles for publication to the journal Reports@SCM, authors accept the following terms:
  1. Authors assign to Societat Catalana de Matemàtiques (a subsidiary of Institut d’Estudis Catalans) the rights of reproduction, communication to the public and distribution of the articles submitted for publication to Reports@SCM.
  2. Authors answer to Societat Catalana de Matemàtiques for the authorship and originality of submitted articles.
  3. Authors are responsible for obtaining permission for the reproduction of all graphic material included in articles.
  4. Societat Catalana de Matemàtiques declines all liability for the possible infringement of intellectual property rights by authors.
  5. The contents published in the journal, unless otherwise stated in the text or in the graphic material, are subject to a Creative Commons Attribution-NonCommercial-NoDerivs (by-nc-nd) 3.0 Spain licence, the complete text of which may be found at https://creativecommons.org/licenses/by-nc-nd/3.0/es/deed.en. Consequently, the general public is authorised to reproduce, distribute and communicate the work, provided that its authorship and the body publishing it are acknowledged, and that no commercial use and no derivative works are made of it.
  6. The journal Reports@SCM is not responsible for the ideas and opinions expressed by the authors of the published articles.