| Finitely generated groups with automatic presentations (2008) | |||||||||||||||
Abstract | |||||||||||||||
| A structure is said to be computable if its domain can be represented by a set which is accepted by a Turing machine and if its relations can then be checked using Turing machines. Restricting the Turing machines in this definition to finite automata gives us a class of structures with a particularly simple computational structure; these structures are said to have automatic presentations. Given their nice algorithmic properties, these have been of interest in a wide variety of areas. An area of particular interest has been the classification of automatic structures. One of the prime examples has been the class of groups. We give a complete characterization in the case of finitely generated groups and show that such a group has an automatic presentation if and only if it is virtually abelian. 1 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||