Polynomial precise interval analysis revisited. (English) Zbl 1258.65048
Albers, Susanne (ed.) et al., Efficient algorithms. Essays dedicated to Kurt Mehlhorn on the occasion of his 60th birthday. Berlin: Springer (ISBN 978-3-642-03455-8/pbk). Lecture Notes in Computer Science 5760, 422-437 (2009).
Summary: We consider a class of arithmetic equations over the complete lattice of integers (extended with \(-\infty \) and \(\infty )\) and provide a polynomial-time algorithm for computing least solutions. For systems of equations with addition and least upper bounds, this algorithm is a smooth generalization of the Bellman-Ford algorithm for computing the single source shortest path in presence of positive and negative edge weights. The method then is extended to deal with more general forms of operations as well as minima with constants. For the latter, a controlled widening is applied at loops where unbounded increase occurs. We apply this algorithm to construct a cubic-time algorithm for the class of interval equations using least upper bounds, addition, intersection with constant intervals as well as multiplication.
For the entire collection see [Zbl 1175.68003].
For the entire collection see [Zbl 1175.68003].
MSC:
| 65G40 | General methods in interval analysis |
References:
| [1] | Cousot, P., Cousot, R.: Static Determination of Dynamic Properties of Programs. In: Second Int. Symp. on Programming, Dunod, Paris, France, pp. 106–130 (1976) · Zbl 0393.68080 |
| [2] | Cousot, P., Cousot, R., Feret, J., Mauborgne, L., Miné, A., Monniaux, D., Rival, X.: The ASTRÉE Analyser. In: Sagiv, M. (ed.) ESOP 2005. LNCS, vol. 3444, pp. 21–30. Springer, Heidelberg (2005) · Zbl 1108.68422 · doi:10.1007/978-3-540-31987-0_3 |
| [3] | Cousot, P., Cousot, R.: Comparison of the Galois Connection and Widening/Narrowing Approaches to Abstract Interpretation. In: JTASPEFL 1991, Bordeaux, vol. 74, pp. 107–110. BIGRE (1991) |
| [4] | Miné, A.: Relational Abstract Domains for the Detection of Floating-Point Run-Time Errors. In: Schmidt, D. (ed.) ESOP 2004. LNCS, vol. 2986, pp. 3–17. Springer, Heidelberg (2004) · Zbl 1126.68353 · doi:10.1007/978-3-540-24725-8_2 |
| [5] | Miné, A.: Symbolic Methods to Enhance the Precision of Numerical Abstract Domains. In: Emerson, E.A., Namjoshi, K.S. (eds.) VMCAI 2006. LNCS, vol. 3855, pp. 348–363. Springer, Heidelberg (2006) · Zbl 1176.68050 · doi:10.1007/11609773_23 |
| [6] | Su, Z., Wagner, D.: A Class of Polynomially Solvable Range Constraints for Interval Analysis Without Widenings. Theor. Comput. Sci. (TCS) 345(1), 122–138 (2005) · Zbl 1078.68154 · doi:10.1016/j.tcs.2005.07.035 |
| [7] | Knuth, D.E.: A Generalization of Dijkstra’s algorithm. Information Processing Letters (IPL) 6(1), 1–5 (1977) · Zbl 0363.68056 · doi:10.1016/0020-0190(77)90002-3 |
| [8] | Gawlitza, T., Seidl, H.: Precise Fixpoint Computation Through Strategy Iteration. In: De Nicola, R. (ed.) ESOP 2007. LNCS, vol. 4421, pp. 300–315. Springer, Heidelberg (2007) · Zbl 1187.68152 · doi:10.1007/978-3-540-71316-6_21 |
| [9] | Leroux, J., Sutre, G.: Accelerated Data-Flow Analysis. In: Riis Nielson, H., Filé, G. (eds.) SAS 2007. LNCS, vol. 4634, pp. 184–199. Springer, Heidelberg (2007) · Zbl 1211.68093 · doi:10.1007/978-3-540-74061-2_12 |
| [10] | Seidl, H.: Least and Greatest Solutions of Equations over \(\mathcal N\) . Nordic Journal of Computing (NJC) 3(1), 41–62 (1996) |
| [11] | Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001) · Zbl 1047.68161 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
