---
_id: '1526'
abstract:
- lang: eng
  text: '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: 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. We show that K-robustness of timed transducers can be decided
    in polynomial space under certain conditions. For asynchronous sequential circuits,
    we reduce K-robustness w.r.t. timed Manhattan distances to K-robustness of discrete
    letter-to-letter transducers and show PSpace-completeness of the problem.'
acknowledgement: This research was supported in part by the European Research Council
  (ERC) under grant 267989 (QUAREM), by the Austrian Science Fund (FWF) under grants
  S11402-N23 (RiSE) and Z211-N23 (Wittgenstein Award), and by the National Science
  Centre (NCN), Poland under grant 2014/15/D/ST6/04543.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
- first_name: Jan
  full_name: Otop, Jan
  id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87
  last_name: Otop
- first_name: Roopsha
  full_name: Samanta, Roopsha
  id: 3D2AAC08-F248-11E8-B48F-1D18A9856A87
  last_name: Samanta
citation:
  ama: 'Henzinger TA, Otop J, Samanta R. Lipschitz robustness of timed I/O systems.
    In: Vol 9583. Springer; 2016:250-267. doi:<a href="https://doi.org/10.1007/978-3-662-49122-5_12">10.1007/978-3-662-49122-5_12</a>'
  apa: 'Henzinger, T. A., Otop, J., &#38; Samanta, R. (2016). Lipschitz robustness
    of timed I/O systems (Vol. 9583, pp. 250–267). Presented at the VMCAI: Verification,
    Model Checking and Abstract Interpretation, St. Petersburg, FL, USA: Springer.
    <a href="https://doi.org/10.1007/978-3-662-49122-5_12">https://doi.org/10.1007/978-3-662-49122-5_12</a>'
  chicago: Henzinger, Thomas A, Jan Otop, and Roopsha Samanta. “Lipschitz Robustness
    of Timed I/O Systems,” 9583:250–67. Springer, 2016. <a href="https://doi.org/10.1007/978-3-662-49122-5_12">https://doi.org/10.1007/978-3-662-49122-5_12</a>.
  ieee: 'T. A. Henzinger, J. Otop, and R. Samanta, “Lipschitz robustness of timed
    I/O systems,” presented at the VMCAI: Verification, Model Checking and Abstract
    Interpretation, St. Petersburg, FL, USA, 2016, vol. 9583, pp. 250–267.'
  ista: 'Henzinger TA, Otop J, Samanta R. 2016. Lipschitz robustness of timed I/O
    systems. VMCAI: Verification, Model Checking and Abstract Interpretation, LNCS,
    vol. 9583, 250–267.'
  mla: Henzinger, Thomas A., et al. <i>Lipschitz Robustness of Timed I/O Systems</i>.
    Vol. 9583, Springer, 2016, pp. 250–67, doi:<a href="https://doi.org/10.1007/978-3-662-49122-5_12">10.1007/978-3-662-49122-5_12</a>.
  short: T.A. Henzinger, J. Otop, R. Samanta, in:, Springer, 2016, pp. 250–267.
conference:
  end_date: 2016-01-19
  location: St. Petersburg, FL, USA
  name: 'VMCAI: Verification, Model Checking and Abstract Interpretation'
  start_date: 2016-01-17
corr_author: '1'
date_created: 2018-12-11T11:52:32Z
date_published: 2016-01-01T00:00:00Z
date_updated: 2025-09-18T11:06:25Z
day: '01'
department:
- _id: ToHe
doi: 10.1007/978-3-662-49122-5_12
ec_funded: 1
external_id:
  arxiv:
  - '1506.01233'
  isi:
  - '000375148800012'
intvolume: '      9583'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://arxiv.org/abs/1506.01233
month: '01'
oa: 1
oa_version: Preprint
page: 250 - 267
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '267989'
  name: Quantitative Reactive Modeling
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: Z211
  name: Formal methods for the design and analysis of complex systems
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S 11407_N23
  name: Rigorous Systems Engineering
publication_status: published
publisher: Springer
publist_id: '5647'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Lipschitz robustness of timed I/O systems
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 9583
year: '2016'
...