zbMATH — the first resource for mathematics

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.
Reviewer: T.Okubo

MSC:
 68Q80 Cellular automata (computational aspects)