Least and greatest solutions of equations over N
Helmut Seidl · Nordic journal of computing · 1996
We 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 ∞), 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.