Edoardo Carta

Abstract: It is known that a system of linear difference equations with coefficients in a finite ring can be recognized by finite automata. Conversely, the states of a finite automaton over a finite ring can be associated with a system of linear difference equations. We generalize this connection in the natural way: rings are generalized by semirings, difference equations by recurrence equations, and automata by transducers. In order to establish the connection between automata and non-homogeneous systems of linear recurrence equations with variable coefficients over a semiring, we introduce the concepts of update automaton and update transducer. The linear transformation induced by a non-homogeneous system is also studied, and solutions for non-homogeneous systems and the composition of two non-homogeneous systems are presented. We also explore the Z-transform and power series representation of these solutions.