Left invertibility of discrete systems with finite inputs and quantised output

Abstract

The aim of this article is to address left invertibility for dynamical systems with inputs and outputs in discrete sets. We study systems which evolve in discrete time within a continuous state-space. Quantised outputs are generated by the system according to a given partition of the state-space, while inputs are arbitrary sequences of symbols in a finite alphabet, which are associated to specific actions on the system. Our main results are obtained under some contractivity hypotheses. The problem of left invertibility, i.e. recovering an unknown input sequence from the knowledge of the corresponding output string, is addressed using the theory of iterated function systems (IFS), a tool developed for the study of fractals. We show how the IFS naturally associated to a system and the geometric properties of its attractor are linked to the invertibility property of the system. Our main result is a necessary and sufficient condition for left invertibility and uniform left invertibility for joint contractive systems. In addition, an algorithm is proposed to recover inputs from output strings. A few examples are presented to illustrate the application of the proposed method.

Keywords:

• left invertibility
• finite inputs
• quantised systems
• attractors
• iterated function systems

Acknowledgements

This work has been partially supported by the European Commission under contract IST 224428 (2008) ‘CHAT - Control of Heterogeneous Automation systems: Technologies for scalability, reconfigurability and security’, and contributes to the goals of CONET, the Cooperating Objects Network of Excellence, contract FP7-2007-2-224053. Authors would like to thank Stefano Marmi (Suola Normale Superiore) for useful discussions.