Distributed lyapunov functions in analysis of graph models of software

Mardavij Roozbehani, Alexandre Megretski, Emilio Frazzoli, Eric Feron

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

9 Scopus citations

Abstract

In previous works, the authors introduced a framework for software analysis, which is basedon optimization of Lyapunov invariants. These invariants prove critical software properties suchas absence of overflow and termination in finite time. In this paper, graph models of softwareare introduced and the software analysis framework is further developed and extended on graphmodels. A distributed Lyapunov function is assigned to the software by assigning a Lyapunovfunction to every node on its graph model. The global decremental condition is then enforced byrequiring that the Lyapunov functions on each node decrease as transitions take place along thearcs. The concept of graph reduction and optimality of graphs for Lyapunov analysis is brieflydiscussed. © 2008 Springer-Verlag Berlin Heidelberg.
Original languageEnglish (US)
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer Verlag
Pages443-456
Number of pages14
ISBN (Print)3540789286
DOIs
StatePublished - Jan 1 2008
Externally publishedYes

Fingerprint Dive into the research topics of 'Distributed lyapunov functions in analysis of graph models of software'. Together they form a unique fingerprint.

Cite this