Structured noncommutative multidimensional linear systems

We introduce a class of multidimensional linear systems with evolution along a free semigroup. The transfer function for such a system is a formal power series in noncommuting indeterminates. Standard system-theoretic properties ( the operations of cascade/parallel connection and inversion, controllability, observability, Kalman decomposition, state-space similarity theorem, minimal state-space realizations, Hankel operators, realization theory) are developed for this class of systems. We also draw out the connections with the much earlier studied theory of rational and recognizable formal power series. Applications include linear-fractional models for classical discrete-time systems with structured, time-varying uncertainty, dimensionless formulas in robust control, multiscale systems and automata theory, and the theory of formal languages.