45852 - Isomorphism problem and automatic groups.

N. Lygeros

  • Post Category:Articles

Question: Is the isomorphism problem solvable for synchronous automatic groups?

Epstein & al conjecture that there is no algorithm that takes as its input two automatic groups and finds out whether they are isomorphic or not.

Hyperbolic groups are automatic.

In fact they are strongly geodesically automatic i.e. there is an automatic structure on the group, where the language accepted by the word acceptor is the set of all geodesic words.

Hyperbolic groups have a solvable word problem since they have a decidable marked isomorphism problem.

But the isomorphism problem is unsolvable for some very natural classes of groups:
the class of free-by-free groups, the class of abelian-by-free groups, but also the class of solvable groups of derived length 3.