Earlier Version
Algorithmic analysis of array-accessing programs
Alur R, Cerny P, Weinstein S. 2009. Algorithmic analysis of array-accessing programs. CSL: Computer Science Logic, LNCS, vol. 5771, 86–101.
Download (ext.)
Conference Paper
| Published
| English
Author
Alur, Rajeev;
Cerny, PavolISTA;
Weinstein, Scott
Series Title
LNCS
Abstract
For programs whose data variables range over boolean or finite domains, program verification is decidable, and this forms the basis of recent tools for software model checking. In this paper, we consider algorithmic verification of programs that use boolean variables, and in addition, access a single read-only array whose length is potentially unbounded, and whose elements range over a potentially unbounded data domain. We show that the reachability problem, while undecidable in general, is (1) Pspace-complete for programs in which the array-accessing for-loops are not nested, (2) decidable for a restricted class of programs with doubly-nested loops. The second result establishes connections to automata and logics defining languages over data words.
Publishing Year
Date Published
2009-09-01
Publisher
Springer
Volume
5771
Page
86 - 101
Conference
CSL: Computer Science Logic
Conference Location
Coimbra, Portugal
Conference Date
2009-09-07 – 2009-09-11
IST-REx-ID
Cite this
Alur R, Cerny P, Weinstein S. Algorithmic analysis of array-accessing programs. In: Vol 5771. Springer; 2009:86-101. doi:10.1007/978-3-642-04027-6_9
Alur, R., Cerny, P., & Weinstein, S. (2009). Algorithmic analysis of array-accessing programs (Vol. 5771, pp. 86–101). Presented at the CSL: Computer Science Logic, Coimbra, Portugal: Springer. https://doi.org/10.1007/978-3-642-04027-6_9
Alur, Rajeev, Pavol Cerny, and Scott Weinstein. “Algorithmic Analysis of Array-Accessing Programs,” 5771:86–101. Springer, 2009. https://doi.org/10.1007/978-3-642-04027-6_9.
R. Alur, P. Cerny, and S. Weinstein, “Algorithmic analysis of array-accessing programs,” presented at the CSL: Computer Science Logic, Coimbra, Portugal, 2009, vol. 5771, pp. 86–101.
Alur R, Cerny P, Weinstein S. 2009. Algorithmic analysis of array-accessing programs. CSL: Computer Science Logic, LNCS, vol. 5771, 86–101.
Alur, Rajeev, et al. Algorithmic Analysis of Array-Accessing Programs. Vol. 5771, Springer, 2009, pp. 86–101, doi:10.1007/978-3-642-04027-6_9.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Google Scholar