Abstract FR:

This work is dedicated to the study of infinite structures (or graphs) which admit a finite presentation. To the equivalences between those presentations and to the geometrical and decidability properties concerning them. The study starts with stack based structures,mainly the prefix recognizable ones. We establish various presentations for those structures, as solutions of equational systems,by transformation of the infinite complete binary tree and by word rewriting. We then study the term-automatic structures and give them,in particular, a new characterization by mean of equational systems. We finally study the families of graphs defined by ground term rewriting. We introduce a new family of graphs of this kind defined as solutions of equational systems. We then study the logics decidable over those graphs and establish some of their geometrical properties.