Lipschitz robustness of timed I/O systems

DOI10.1007/978-3-662-49122-5_12MaRDI QIDQ2796054zbMATH OpenOpenAlexFDO

Authors Jan Otop, Roopsha Samanta, Thomas A. Henzinger

Publication date 23 March 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1506.01233

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Abstract: We present the first study of robustness of systems that are both timed as well as reactive (I/O). We study the behavior of such timed I/O systems in the presence of "uncertain inputs" and formalize their robustness using the analytic notion of Lipschitz continuity. Thus, a timed I/O system is K-(Lipschitz) robust if the perturbation in its output is at most K times the perturbation in its input. We quantify input and output perturbation using "similarity functions" over timed words such as the timed version of the Manhattan distance and the Skorokhod distance. We consider two models of timed I/O systems --- timed transducers and asynchronous sequential circuits. While K-robustness is undecidable even for discrete transducers, we identify a class of timed transducers which admits a polynomial space decision procedure for K-robustness. For asynchronous sequential circuits, we reduce K-robustness w.r.t. timed Manhattan distances to K-robusness of discrete letter-to-letter transducers and show PSPACE-compeleteness of the problem.

Recommendations

• Lipschitz robustness of finite-state transducers
• Robustness in timed automata
• Robustness of time Petri nets under guard enlargement
• Robust Computations with Dynamical Systems
• Robustness of time Petri nets under guard enlargement

Cited in

(3)

• Model measuring for discrete and hybrid systems
• Robustness analysis of networked systems
• Lipschitz robustness of finite-state transducers

This page was built for publication: Lipschitz robustness of timed I/O systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2796054)