Mapping class groups are automatic. (English) Zbl 0867.57004

Let \(S\) be a compact surface with a finite set (possibly empty) of punctures \(P\) removed. The main result of the paper says that the mapping class group of \(S\), \({\mathcal M} {\mathcal C} {\mathcal G}(S)\), is automatic. An automatic structure on a group \(G\) is a finite set \(A\) of generators together with a set \(L\) of words in the letters of \(A\), called normal forms, such that each element of \(G\) is represented by at least one normal form, and such that finite deterministic automata may be used to decide whether a given word in the letters of \(A\) is a normal form, whether two normal forms represent equal elements in \(G\), and whether two normal forms represent elements in \(G\) differing by a given generator. A general automatic group has a quadratic time algorithm for the word problem and satisfies certain nice geometric properties; for example the isoperimetric function is quadratically bounded.


57M07 Topological methods in group theory
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
Full Text: DOI