Solving difference equations whose coefficients are not transcendental

We consider a large class of sequences which are defined by systems of (possibly nonlinear) difference equations. A procedure for recursively enumerating the algebraic dependencies of such sequences is presented. Also a procedure for solving linear difference equations with such sequences as coefficients is proposed. The methods are illustrated on some problems arising in the literature on special functions and combinatorial sequences.