AbstractWe consider the problem of computing least and greatest solutions of a system of equations

x_{i}=f_{i},i= 1,...,n, overN, i.e., the naturals (extended byinfty), where the right hand sidesf_{i}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.