English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  Thread-Modular Verification is Cartesian Abstract Interpretation

Malkis, A., Podelski, A., & Rybalchenko, A. (2006). Thread-Modular Verification is Cartesian Abstract Interpretation. In Theoretical aspects of computing - ICTAC 2006 : third International Colloquium (pp. 183-197). Berlin, Germany: Springer.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2430-F Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2432-B
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Malkis, Alexander1, Author           
Podelski, Andreas1, Author           
Rybalchenko, Andrey1, Author           
Barkaoui, Kamel, Editor
Cavalcanti, Ana, Editor
Cerone, Antonio, Editor
Affiliations:
1Programming Logics, MPI for Informatics, Max Planck Society, ou_40045              

Content

show
hide
Free keywords: -
 Abstract: Verification of multithreaded programs is difficult. It requires reasoning about state spaces that grow exponentially in the number of concurrent threads. Successful verification techniques based on modular composition of over-approximations of thread behaviors have been designed for this task. These techniques have been traditionally described in assume-guarantee style, which does not admit reasoning about the abstraction properties of the involved compositional argument. Flanagan and Qadeer thread-modular algorithm is a characteristic representative of such techniques. In this paper, we investigate the formalization of this algorithm in the framework of abstract interpretation. We identify the abstraction that the algorithm implements; its definition involves Cartesian products of sets. Our result provides a basis for the systematic study of similar abstractions for dealing with the state explosion problem. As a first step in this direction, our result provides a characterization of a minimal increase in the precision of the Flanagan and Qadeer algorithm that leads to the loss of its polynomial complexity.

Details

show
hide
Language(s): eng - English
 Dates: 2007-04-262006
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 314594
Other: Local-ID: C1256104005ECAFC-96547D152FE0A906C12572250048F51F-malkis2006
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Tunis, Tunisia
Start-/End Date: 2006-11-20

Legal Case

show

Project information

show

Source 1

show
hide
Title: Theoretical aspects of computing - ICTAC 2006 : third International Colloquium
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Berlin, Germany : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 183 - 197 Identifier: ISBN: 978-3-540-48815-6

Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 4281 Sequence Number: - Start / End Page: - Identifier: -