AbstractWe consider the problem of computing least and greatest solutions of a system of equations xi = fi, i = 1,...,n, over N, i.e., the naturals (extended by infty), where the right hand sides fi are expressions built up from constants and variables by various sets of operations.
We present efficient algorithms in case where the following operations occur:
(1) minimum and maximum;
(2) maximum, addition and multiplication;
(3) minimum, addition and multiplication;
(4) minimum, maximum, addition and multiplication.
We extend the methods to the cases where (one-sided) conditionals are allowed as well.
Categories and Subject Descriptors: D.3.4 [Programming Languages]: Processors; F.4.1 [Mathematical Logic and Formal Languages]: Mathematical Logic; G.2.1 [Discrete Mathematics]: Combinatorics
Additional Key Words and Phrases: equations over integers, least or greatest solution, program analysis
Selected papers that cite this one
- H. Seidl and M. H. Sørensen. Constraints to stop deforestation. Science of Computer Programming, 32(1-3):73-107, September 1998.
Selected references
- B. Courcelle and M. Mosbah. Monadic second-order evaluations on tree-decomposable graphs. Theoretical Computer Science, 109(1-2):49-82, 1 March 1993.
- Patrick Cousot and Radhia Cousot. Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Conference Record of the Fourth ACM Symposium on Principles of Programming Languages, pages 238-252, Los Angeles, California, January 1977.
- Patrick Cousot and Radhia Cousot. Abstract interpretation and application to logic programs. Journal of Logic Programming, 13(2-3):103-179, July 1992.
- Michael L. Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3):596-615, July 1987.
- Annegret Habel, Hans-Jörg Kreowski, and Walter Vogler. Decidable boundedness problems for sets of graphs generated by hyperedge-replacement. Theoretical Computer Science, 89(1):33-62, 21 October 1991.
- Sebastian Hunt and Chris Hankin. Fixed points and frontiers: a new perspective. Journal of Functional Programming, 1(1):91-120, January 1991.
- Thomas J. Marlowe and Barbara G. Ryder. Properties of data flow frameworks. Acta Informatica, 28(2):121-163, 1990.
- Hanne Riis Nielson and Flemming Nielson. Bounded fixed-point iteration. Journal of Logic and Computation, 2(4):441-464, August 1992.
- Helmut Seidl. Finite tree automata with cost functions. Theoretical Computer Science, 126(1):113-142, 11 April 1994.