Files in this item

FilesDescriptionFormat

application/pdf

application/pdfvmcai.pdf (232kB)
Main PaperPDF

Description

Title:Complexity bounds for the verification of real-time software
Author(s):Chadha, Rohit; Legay, Axel; Prabhakar, Pavithra; Viswanathan, Mahesh
Subject(s):Complexity
Verification
Real-time software
Succint Representations
Boolean Automata
Abstract:We present uniform approaches to establish complexity bounds for decision problems such as reachability and simulation, that arise naturally in the verification of timed software systems. We model timed software systems as timed automata augmented with a data store (like a pushdown stack) and show that there is at least an exponential blowup in complexity of verification when compared with untimed systems. Our proof techniques also establish complexity results for boolean programs, which are automata with stores that have additional boolean variables.
Issue Date:2009
Publisher:Springer Verlag
Citation Info:Eleventh International Conference on Verification, Model Checking, and Abstract Interpretation
Genre:Technical Report
Type:Text
Language:English
URI:http://hdl.handle.net/2142/14134
Publication Status:published or submitted for publication
Peer Reviewed:is peer reviewed
Date Available in IDEALS:2009-10-30


This item appears in the following Collection(s)

Item Statistics