Least Solutions of Equations over N Helmut Seidl

Abstract. We consider the problem of computing the least solution Xi, i = 1,..., n, 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 operations taken from some set Ω. We present efficient algorithms for various subsets Ω of the operations minimum, maximum, addition and multiplication.