In this paper, we propose algorithms that extend a given  regular tree grammar G0 
to a new grammar G respecting the following two properties:
(i) G belongs to  the sub-class of local or single-type tree grammars and
(ii) G  is the least grammar (in the sense of language inclusion) that contains the language of G0.
Our algorithms give rise to   important tools in the context of web service  composition or XML schema evolution.
We are particularly interested in applying them in order to reconcile different XML type messages among services.
The algorithms are proven correct and some of their applications are discussed.