Reachability in Linear Recurrence Automata

This paper studies the linear recurrence automata model in which multiple linear recurrences can be used to generate sequences of numbers. We parameterised the model by varying several structural properties to identify under which constraints or extensions the reachability problems become computationally hard and undecidable. We show first the reduction of classical matrix semigroup problems to reachability in linear recurrence automata and then analyse several variants of the model restricting the state structures, the number and the depth of recurrences.