A Caltech Library Service

A Framework for Robust Stability of Systems Over Finite Alphabets

Tarraf, Danielle C. and Megretski, Alexandre and Dahleh, Munther A. (2008) A Framework for Robust Stability of Systems Over Finite Alphabets. IEEE Transactions on Automatic Control, 53 (5). pp. 1133-1146. ISSN 0018-9286. doi:10.1109/TAC.2008.923658.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© Copyright 2008 IEEE. Reprinted with permission. Manuscript received February 15, 2006; revised March 18, 2007 and October 18, 2007. Published August 27, 2008 (projected). [Date Published in Issue: 2008-08-26] Recommended by Associated Editor C. Abdallah. This research was supported by the Air Force Aerospace Research-OSR Grant FA9550-04-1-0052 while the first author was at MIT. The first author would like to thank V.D. Blondel and P.A. Parrilo for helpful discussions about network flow problems. The authors would like to thank the Associate Editor and the anonymous reviewers for valuable feedback and suggestions for improving the paper.
Funding AgencyGrant Number
Air Force Office of Scientific ResearchFA9550-04-1-0052
Subject Keywords:Dissipative system, finite state machine, incremental stability, input/output stability, shortest path problem, small gain theorem, storage functions, system over finite alphabet
Issue or Number:5
Record Number:CaltechAUTHORS:TARieeetac08
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:11692
Deposited By: Archive Administrator
Deposited On:19 Sep 2008 21:32
Last Modified:08 Nov 2021 22:01

Repository Staff Only: item control page