Operations on the tree representations of piecewise quasi-affine functions

The piecewise quasi-affine (PQAF) functions and PQAF-sets are considered. Tree representation of PQAF-function and PQAF-set and its complexity are introduced. The algorithms of union, intersection, empty check, sum, image/preimage calculation, inversion, composition, and comparison are given. The algorithms are provided with complexity estimates of the resulting objects. A theorem about the type and complexity of lexicographical extrema in the PQAF-set, depending on the parameters, has been proved.