О разложениях корневых деревьев

Работа посвящена разложениям корневых деревьев, характеризующихся весами висячих вершин и приписанными внутренним вершинам функциональными символами, по которым рекуррентно определяются веса этих вершин. Такими деревьями удобно представлять формулы: при этой интерпретации разложения соответствуют представлениям формулы в виде суперпозиции, а веса отражают меру сложности. Рассмотрены экстремальные задачи типа минимизации числа частей разложения при естественных ограничениях. Некоторые из них допускают точные эффективные алгоритмы, для других доказана NP-трудность и оценена погрешность приближенных алгоритмов. Исследован вопрос о наибольшем числе частей разложения при фиксированных количестве вершин и некоторых параметрах разложений; результаты уточнены для бинарных деревьев.