Parsimonious, simulation based verification of linear systems

Parasara Sridhar Duggirala, Mahesh Viswanathan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We present a technique to verify safety properties of linear systems (possibly time varying) using very few simulations. For a linear system of dimension n, our technique needs n + 1 simulation runs. This is in contrast to current simulation based approaches, where the number of simulations either depends upon the number of vertices in the convex polyhedral initial set, or on the proximity of the unsafe set to the set of reachable states. At its core, our algorithm exploits the superposition principle of linear systems. Our algorithm computes both an over and an under approximation of the set of reachable states.

Original languageEnglish (US)
Title of host publicationComputer Aided Verification - 28th International Conference, CAV 2016, Proceedings
EditorsAzadeh Farzan, Swarat Chaudhuri
PublisherSpringer
Pages477-494
Number of pages18
ISBN (Print)9783319415277
DOIs
StatePublished - Jan 1 2016
Event28th International Conference on Computer Aided Verification, CAV 2016 - Toronto, Canada
Duration: Jul 17 2016Jul 23 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9779
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other28th International Conference on Computer Aided Verification, CAV 2016
Country/TerritoryCanada
CityToronto
Period7/17/167/23/16

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Parsimonious, simulation based verification of linear systems'. Together they form a unique fingerprint.

Cite this