Abstract FR:

On etudie differentes classes de complexes simpliciaux infinis constructifs, d'un point de vue algorithmique. Premierement, nous etudions les surfaces non-compactes sans bord definies, en termes de triangularisations, par des grammaires de remplacement d'hyperarcs : les surfaces hr-equationnelles. Nous donnons un algorithme pour decider si deux telles surfaces sont homeomorphes ou non. Ensuite, nous abordons le cas des surfaces non-compactes a bord. A cet egard, nous generalisons le theoreme de classification de kerekjarto-richards au cas des surfaces non-compactes planaires a bord. Dans une deuxieme partie, nous etudions le cas de la dimension 3. Nous montrons que les 3-varietes hr-equationnelles qui possedent une structure hyperbolique complete sont essentiellement caracterisees a isometrie pres par leurs groupes fondamentaux. Nous abordons ensuite l'etude de ces groupes qui se revelent etre des produits amalgames arborescents de groupes, en nombre infini, mais neanmoins en nombre fini a isomorphisme pres. On s'attache en particulier a en donner des presentations constructives en termes de langages rationnels. Pour finir, nous abordons le cas des graphes automatiques qui generalisent les graphes hr-equationnels. Nous montrons que determiner le nombre de bouts d'un tel graphe est un probleme indecidable. Par ailleurs, nous montrons que ce probleme est equivalent au probleme de determiner si un dol-systeme de graphes ne donne naissance qu'a des graphes connexes ; cette question devient alors aussi indecidable.