Rafail Ostrovsky - Publications

Error-Correcting Codes for Automatic Control

Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman


In many control-theory applications one can classify all possible states of the device by an infinite state graph with polynomially-growing expansion. In order for a controller to control or estimate the state of such a device, it must receive reliable communications from its sensors; if there is channel noise, the encoding task is subject to a stringent real-time constraint. We show a constructive on-line error correcting code that works for this class of applications. Our code is is computationally efficient and enables on-line estimation and control in the presence of channel noise. It establishes a constructive (and optimal-within-constants) analog, for control applications, of the Shannon coding theorem.

comment: Appeared in Proceedings of 46st Annual IEEE Symposium on the Foundations of Computer Science (FOCS-2005).

Fetch PostScript file of the paper     Fetch PDF file of the paper

Back to the Rafail Ostrovsky publication list or to the Rafail Ostrovsky main page.