ОПЕРАЦИИ НАД ПРЕДСТАВЛЕНИЯМИ КУСОЧНО-КВАЗИАФФИННЫХ ФУНКЦИЙ В ВИДЕ ДЕРЕВЬЕВ

Введены понятия кусочно заданной квазиаффинной (ККА) функции и ККА-множества. Определены представления ККА-множеств и ККА-функций в виде деревьев и понятие сложности представления. Описаны алгоритмы выполнения операций над древовидными представлениями, в частности объединение, пересечение, проверка ККА-множества на пустоту, сумма, вычисление образа/прообраза, обращение, суперпозиция, сравнение ККА-функций. Даны оценки сложности получающихся в результате объектов. Доказана теорема о виде и сложности лексикографического экстремума в ККА-множестве, зависящем от параметров.