The Library
On model checking data-independent systems with arrays with whole-array operations
Tools
Lazic, Ranko, Newcomb, Tom and Roscoe, A. W. (2005) On model checking data-independent systems with arrays with whole-array operations. In: Abadallah, A. E. and Jones, C. B. and Sanders, J. W., (eds.) Communicating Sequential Processes. The First 25 Years. Lecture Notes in Computer Science, Volume 3525 . Springer Berlin Heidelberg, pp. 275-291. ISBN 9783540258131
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/11423348_17
Abstract
We consider programs which are data independent with respect to two type variables X and Y, and can in addition use arrays indexed by X and storing values from Y. We are interested in whether a program satisfies its control-state unreachability specification for all non-empty finite instances of X and Y. The decidability of this problem without whole-array operations is a corollary to earlier results.
We address the possible addition of two whole-array operations: an array reset instruction, which sets every element of an array to a particular value, and an array assignment or copy instruction. For programs with reset, we obtain decidability if there is only one array or if Y is fixed to be the boolean type, and we obtain undecidability otherwise. For programs with array assignment, we show that they are more expressive than programs with reset, which yields undecidability if there are at least three arrays. We also obtain undecidability for two arrays directly.
Item Type: | Book Item | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Series Name: | Lecture Notes in Computer Science | ||||
Publisher: | Springer Berlin Heidelberg | ||||
ISBN: | 9783540258131 | ||||
ISSN: | 0302-9743 | ||||
Book Title: | Communicating Sequential Processes. The First 25 Years | ||||
Editor: | Abadallah, A. E. and Jones, C. B. and Sanders, J. W. | ||||
Official Date: | 2005 | ||||
Dates: |
|
||||
Volume: | Volume 3525 | ||||
Number of Pages: | 17 | ||||
Page Range: | pp. 275-291 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Title of Event: | Symposium on 25 Years of Communicating Sequential Processes | ||||
Location of Event: | London S Bank Univ, London, England | ||||
Date(s) of Event: | 07-08 Jul 2004 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |