О сложности последовательной реализации частичных булевых функций схемами

Пара $(f,g)$ частичных булевых функций характеризуется параметром $l_{\alpha,\beta}$ – числом наборов $\widetilde x$, на которых $(f(\widetilde x),g(\widetilde x))=(\alpha,\beta)$, где $\alpha$ и $\beta$ принимают значения 0, 1 и неопределённое. Рассматривается последовательная реализация системы $(f,g)$, когда сначала строится схема $S_f$ для $f$, которая затем достраивается до схемы $S_{f,g}$. Показано, что если область определения $D(f)$ включает $D(g)$, то можно последовательно реализовать $f$ и $g$ так, чтобы схемы $S_f$ и $S_{f,g}$ были одновременно асимптотически минимальными (т.е. удовлетворяли асимптотически наилучшим оценкам сложности для соответствующих классов), и что эти функции, вообще говоря, нельзя последовательно реализовать в порядке $g$, $f$, чтобы асимптотически минимальными были $S_g$ и $S_{f,g}$. Получена достижимая нижняя оценка сложности схем $S_{f,g}$ при последовательной реализации. Существенную роль играют информационные свойства частично определённых данных, изучение которых начато в предшествующих работах автора и продолжено здесь.
Библ. 12.