Linear recurrence equations on a tree. (Q2508728)

The notion of a system of linear recurrences on a tree is defined. In the particular case of the tree being a ray and the assigned vector spaces being one dimensional, the system of linear recurrences can be understood in the ordinary way. The main result of the paper is that there exists an algorithm that tests a system of recurrence equations on a tree for the existence of a nontrivial solution and computes one of these solutions (Theorem 1). From the theorem follows the existence of several algorithms for recognition of some properties of elements of any monomial automaton algebra. Remark: The result ``The equality problem is solvable if the ideal of relations is specified by a finite Gröbner [Gröbner-Shirshov -- L.B.] basis'' (see p. 603) must be attributed to \textit{A. I. Shirshov} [Sib. Mat. Zh. 3, 292-296 (1962; Zbl 0104.26004)].