Algorithmic Study of Infinite Simplicial Complexes

Olivier Ly

PhD Thesis -
LaBRI - Bordeaux I university
Supervisors: G. Senizergues and P. Narbel

Keywords : automatic graphs - non-compact manifolds


We study different classes of constructive infinite simplicial complexes, from an algorithmic point of vue. Firstly, we study the triangulated non-compact surfaces without boundary whose triangulations are defined by some hyperedge replacement graph grammars: the HR-equational surfaces. We give an algorithm to decide whether two such surfaces are homeomorphic or not.

Then, we look at the case of bordered non-compact surfaces. To this respect, we generalize the classification theorem of Kerékjarto-Richards to the case of planar non-compact surfaces.

In the second part, we study the case of 3-dimensional manifolds. We show that HR-equational non-compact hyperbolic 3-manifolds are essentially characterized by their fundamental groups. We then study these groups which are amalgamated products of infinitely many groups, but in finite number up to isomorphism. In particular, we define for them some constructive presentations given in terms of rational languages.

The last part of our work is devoted to automatic graphs which generalize HR-equational graphs. To this respect, we show that the problem of deciding whether an automatic graph has more than one end is undecidable. On the other hand, we show that this problem is equivalent to the one of determining whether all the graphs generated by a given graph D0L-system are connected. It turns out that this last question is also undecidable.


whole document: (2.5M pdf)

- home -