Some systems of simultaneous linear recurrences and their applications to computing of graph expression lengths

The paper proposes techniques which provide closed-form solutions for special simultaneous systems of two and three linear recurrences. These systems are characterized by particular restrictions on their coefficients. We discuss the application of these systems to some algorithmic problems associated with relationship between algebraic expressions and graphs. Using decomposition methods described in the paper we generate the simultaneous recurrences for graph expression lengths and solve them with the proposed approach.