Computers, groups and hyperbolic geometry.

*(English)*Zbl 0673.68036
On the geometry of differentiable manifolds, Workshop, Rome/Italy 1986, Astérisque 163-164, 9-29 (1988).

[For the entire collection see Zbl 0666.00013.]

By making use of computer science, a speedy algorithmic approach to certain questions in group theory is produced, e.g. it would take hours for a tessellation of the hyperbolic plane by triangles with angles \(\pi\) /2, \(\pi\) /3, \(\pi\) /7, whereas the current program, incorporating the new schemes mentioned, takes only 5 minutes.

Let G be a group of hyperbolic isometries acting on a 3-dimensional manifold M. If \(\{x_ 1,...,x_ n\}\) is the generator of G, then the set \(I=\{x_ 1,...,x_ n,x_ 1^{-1},...,x_ n^{-1}\}\) is the alphabet in the terminology of computer science, and a language L over I is any subset of \(I^*\) \((=the\) free non-abelian semigroups with identity generated by I). Introducing the operations “union” and “concatenation” and also the Kleene closure, L is made into a regular language. The deterministic finite automation (written as DFA for short) consists of I, a finite set of states, an initial state \(M_ 0\), a subset A of accepting states. Then, as is well-known, the language L(M) is regular if DFA, M, is given. We say that G is an automatic group if there are \((n+2)\) DFA’s W, \(M_ 0,M_ 1,...,M_ n\) such that \(M_ i\) recognizes multiplication by \(x_ i\) for \(1\leq i\leq n\), and call the form \((G,\{x_ 1,...,x_ n\},W,M_ 0,...,M_ n)\) an automatic structure on G. If G is now a fundamental group of a compact hyperbolic 3-manifold M, then the (acceptable) language corresponding to W of the automatic structure consists of all words in the generators which are shortest words, and this implies geometrically that they are nothing but geodesics in the Cayley group \(\Gamma\) of M issuing from the identity. Thus geometry of M can be proceeded much faster by means of such automatic structure defined on a group of M.

By making use of computer science, a speedy algorithmic approach to certain questions in group theory is produced, e.g. it would take hours for a tessellation of the hyperbolic plane by triangles with angles \(\pi\) /2, \(\pi\) /3, \(\pi\) /7, whereas the current program, incorporating the new schemes mentioned, takes only 5 minutes.

Let G be a group of hyperbolic isometries acting on a 3-dimensional manifold M. If \(\{x_ 1,...,x_ n\}\) is the generator of G, then the set \(I=\{x_ 1,...,x_ n,x_ 1^{-1},...,x_ n^{-1}\}\) is the alphabet in the terminology of computer science, and a language L over I is any subset of \(I^*\) \((=the\) free non-abelian semigroups with identity generated by I). Introducing the operations “union” and “concatenation” and also the Kleene closure, L is made into a regular language. The deterministic finite automation (written as DFA for short) consists of I, a finite set of states, an initial state \(M_ 0\), a subset A of accepting states. Then, as is well-known, the language L(M) is regular if DFA, M, is given. We say that G is an automatic group if there are \((n+2)\) DFA’s W, \(M_ 0,M_ 1,...,M_ n\) such that \(M_ i\) recognizes multiplication by \(x_ i\) for \(1\leq i\leq n\), and call the form \((G,\{x_ 1,...,x_ n\},W,M_ 0,...,M_ n)\) an automatic structure on G. If G is now a fundamental group of a compact hyperbolic 3-manifold M, then the (acceptable) language corresponding to W of the automatic structure consists of all words in the generators which are shortest words, and this implies geometrically that they are nothing but geodesics in the Cayley group \(\Gamma\) of M issuing from the identity. Thus geometry of M can be proceeded much faster by means of such automatic structure defined on a group of M.

Reviewer: T.Okubo

##### MSC:

68Q80 | Cellular automata (computational aspects) |