A Framework for Robust Stability of Systems Over Finite Alphabets

Systems over finite alphabets are discrete-time systems whose input and output signals take their values in finite sets. Three notions of input/output stability (gain stability, incremental stability and external stability) that are particularly applicable to this class of systems are proposed and motivated through examples. New formulations for generalized small gain and incremental small gain theorems are presented, thus showing that gain stability and incremental stability are useful robustness measures. The paper then focuses on deterministic finite state machine (DFM) models. For this class, the problems of verifying gain stability, incremental stability, and corresponding gain bounds are shown to reduce to searching for an appropriate storage function. These problems are also shown to be related to the problem of verifying the nonexistence of negative cost cycles in an appropriately constructed network. Using this insight and based on a solution approach for discrete shortest path problems, a strongly polynomial algorithm is proposed. Finally, incremental stability and external stability are shown to be equivalent notions for this class of systems.