Properties of Algorithmic Operators.
Vladimir B. Borshchev · 1991
We consider operators working on lattices of interpretations of logic programs. Operators defined by programs are called algorithmic. Some properties of algorithmic operators, such as monotonicity and compactness, are used to define fix-point semantics. But what are necessary and sufficient conditions for such operators? The main result of this paper may be formulated, roughly speaking, as follows: an operator is algorithmic, iff its result on a given interpretation is the sum of its results on finite and restricted parts of this interpretation, i.e., is in essence defined by a certain algebra. This condition, which we called as n,k-truncateness of an operator, may be divided into several simpler conditions dealing with the generalisation of the notion of monotonicity and with the “breadth” n (the maximum number of terms) and the “height” k (the maximum height of terms) of subsystems which form the result of the operator.