Автоматная сложность булевых функций из классов Поста тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Кибкало, Мария Александровна

• Кибкало, Мария Александровна
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Кибкало, Мария Александровна

Оглавление

Введение

§ 1. Общая характеристика задачи

§ 2. Основные понятия и обозначения

§ 3. Основные результаты

Глава 1. Методы построения сложных автоматов и функций

§1.1. Слияние прямого и обратного деревьев

§ 1.2. Вставка переменных

§ 1.3. Вставка //-ядра 39 § 1.4. Вложение двоичного куба

в множество монотонных функций

§ 1.5. Слияние Агарных деревьев 45 § 1.6. Зависимость высоты обратного дерева

от числа переменных 48 Глава 2. Точные значения и асимптотика функции Шеннона

классов Поста

§2.1. Классы С1, С2, С3, С4 всех булевых функций и функций,

сохраняющих 0 и/или 1

§ 2.2. Классы 0г,03 самодвойственных функций

§ 2.3. Классы F7°0 функций, обладающих свойством <Л°°> и (а°°)

§ 2.4. Классы ¥2, функций, обладающих свойством {А2) и (а2) 62 § 2.5. Классы А1,А2,А3,А4 всех монотонных функций

и монотонных функций, сохраняющих 0 и/или 1 67 § 2.6. Классы Р2 монотонных функций,

обладающих свойством {А2) и (а2)

§ 2.7. Класс £>2 монотонных самодвойственных функций 78 § 2.8. Классы монотонных функций,

обладающих свойством (Ат) и (а00) 81 § 2.9. Метод вставки переменных

для множеств ^У7/4*1,= 1,4,5,8

§ 2.10. Метод вставки //-ядра для множеств у = 1,4,5,8

§ 2.11. Метод вставки переменных

для множеств = 2,3,6,7

§ 2.12. Метод вставки /л-ядра для множеств у = 2,3,6,7

Глава 3. Сложность коллекций языков

§ 3.1. Сложность коллекций языков длины п

§ 3.2. Сложность коллекций языков длины не более п

Глава 4. Сравнение с другими мерами сложности

§ 4.1. Сложность покрывающих автоматов

§ 4.2. Сложность полиномов Жегалкина

§ 4.3. Коррелирующие меры сложности

§ 4.4. Результаты для упорядоченных диаграмм решений

Заключение

Приложение А. Алгоритмы и формулы

для вычисления высоты обратного дерева

Приложение В. Таблицы сложности классов Поста 115 Приложение С. Таблицы сложности

функций из множеств

Список рисунков

Список литературы

Список составлен в порядке упоминания работ в тексте диссертации

Введение диссертации (часть автореферата) на тему «Автоматная сложность булевых функций из классов Поста»

Введение

§ 1. Общая характеристика задачи

Теоретическое осмысление вопросов программирования привело к необходимости измерять сложность подлежащих моделированию объектов. Ограниченная производительность вычислительных систем привела к преимущественному использованию для этих целей линейных методов распознавания, фильтрации, кодирования и предсказания поведения объектов. Действительно, линейные методы быстро суммируют вклады признаков, перекладывая качественную часть работы на исследователей, изобретающих эти удачные признаки. Заметим, что и сложность вычислений в линейных методах также линейно зависит от размерности задачи. Однако при таком подходе много времени затрачивается на творческие, интеллектуально сложные работы в предметной области, которые хотелось бы автоматизировать.

Понимание того, что линейных методов недостаточно привело к широкому использованию термина «нелинейные». При этом нелинейными часто называют либо пороговые методы, либо булевы функции, в полиноме которых присутствуют два-три члена второй степени. Широкому использованию произвольных нелинейных методов препятствует их высокая сложность. При их реализации приходится выполнять экспоненциально растущее от входных данных число операций.

При реализации вычислений в процессорах естественным образом происходит переход от математики непрерывной к математике булевой. За пару десятилетий процессоры прошли путь из 16-битных к 32-битным, а затем - к 64-битным. Какие затраты необходимы для 2к-битного процессора можно узнать, оценив в том числе и сложность булевых функций от 2К переменных, реализующих команды процессора.

Поскольку передача данных по каналам связи происходит последовательно, актуален вопрос о последовательном вычислении булевых

функций по мере появления значений их переменных, то есть о вычислении булевых функций автоматами или двоичными диаграммами решений (binary decision diagram). Эта задача была поставлена еще в 1955 году Олегом Борисовичем Лупановым [1].

За последнее десятилетие по сложности двоичных диаграмм решений появилось огромное число работ, так как это сложность реализации функций в небольших устройствах, что, как правило, приводит к коммерческому успеху. Тем не менее, оценка автоматной сложности классов Поста оставалась вне поля зрения исследователей. Этот пробел заполняет настоящая работа.

Одной из основных задач математической кибернетики является оптимальное представление дискретных процессов в различных моделях [2]. Среди используемых моделей особое место занимают конечные автоматы.

Современное понятие конечного автомата окончательно сформировалось в результате исследования дискретных преобразователей информации, поведение которых зависит от входа за последние несколько моментов времени [3,4,5]. Конечные автоматы успешно использовались для моделирования различных объектов (например, ограниченно-детерминированных функций и регулярных языков) и операций с ними [6,7,8]. Одним из важнейших разделов теории автоматов является изучение различных мер сложности (например, времени решения проблемы, числа операций для построения автомата или количества состояний автомата) [9,10,11]. Настоящая работа посвящена последнему виду сложности автоматов, моделирующих конечные языки и булевы функции.

Конечные автоматы могут использоваться для представления не только регулярных, но и конечных языков, а также булевых и &-значных функций. В этом случае наборы, на которых функция не равна 0, рассматриваются как слова одного или нескольких конечных языков. Сложность языка (функции) определяется как сложность представляющего его (ее) приведенного автомата. При этом естественным образом определяется функция Шеннона для класса (множества) языков или функций.

Следует отметить, что конечный автомат является слишком мощной моделью для представления функций:

• Конечный автомат способен преобразовывать входной регулярный язык в выходной регулярный язык, тогда как автомат-акцептор, фактически, преобразует входной язык в язык, слова которого состоят из одного символа. Другими словами, функция выхода используется только при переходе в тупиковое состояние.

• Диаграмма конечного автомата, в принципе, может содержать циклы, что позволяет моделировать бесконечные языки. Диаграмма автомата, представляющего булеву функцию, не содержит циклов (кроме перехода из тупикового состояния в себя).

Конечный автомат обладает свойствами, которые естественны для моделирования языков и не всегда удобны при моделировании функций:

• Конечный автомат не симметричен относительно слов входящих и не входящих в язык. Для булевой функции это проявляется в несимметричности значений 0 и 1 в модели, из-за которой при определении сложности автомата нужно отдельно учитывать состояния, эквивалентные тупиковому. С другой стороны, несимметричность сделала возможным построение покрывающих автоматов, позволяющих уменьшать сложность модели [12].

• Конечный автомат, моделирующий булеву функцию, не симметричен относительно символов в словах языка (переменных функции). Для функции, в общем случае, переменные равноправны.

Эти причины привели к использованию для моделирования булевых функций формализма двоичных диаграмм решений (Binary Decision Diagrams -BDD) или ветвящихся программ (Branching Programs - BP), впервые примененному Брайантом в [13]. Обзор свойств и особенностей различных видов BDD дан в диссертации Грёпля, посвященной эффекту Шеннона для сложности OBDD [14]. К автоматному представлению булевых функций ближе всего наиболее популярный тип диаграмм решений - так называемые упорядоченные двоичные диаграммы решений (Ordered Binary Decision Diagrams или OBDD)

постоянной высоты. Такой способ отличается от представления функций конечным автоматом лишь несущественными деталями [15,16]. Вместо функции выхода в OBDD определяются выходные состояния (два выходных состояния в случае булевых функций). В отличие от состояний конечного автомата, реагирующих на очередной входной символ, состояния OBDD реагируют на переменную с определенным номером. Модель булевой функции в виде OBDD симметрична относительно значений функции 0 и 1. Такая модель, в определенном смысле, симметрична относительно переменных функции: можно выбрать любой фиксированный порядок переменных. Это привело к появлению нового класса задач о выборе оптимального порядка переменных, которому посвящена большая часть работ по тематике OBDD.

Аналогично автоматной модели, сложность функции, представляемой OBDD, определяется как число состояний в единственно возможной диаграмме приведенного вида. Для приведения OBDD используются операции слияния и удаления состояний. Слиянию подвергаются состояния, являющиеся вершинами эквивалентных поддиаграмм (это возможно лишь для состояний, соответствующих одной переменной). В результате получается квазисокращенная диграмма решений (Quasi-Reduced ODBB или QROBDD). Она отличается от диаграммы приведенного автомата возможным добавлением состояний, автоматно эквивалентных тупиковому. Операция удаления состояний, приводящая к построению сокращенной диаграммы решений (Reduced ODBB или ROBDD), исключает из диаграммы состояния с тождественной функцией перехода.

В диссертации рассматриваются как булевы и А>значные функции (языки из слов постоянной длины), так и языки из слов переменной длины. Поэтому, при построении сложных функций и языков мы будем использовать формализм конечных автоматов. OBDD, представляющие такие функции, будут иметь ту же асимптотику сложности и некоторые отличия в точных формулах.

Сложности автоматов и диаграмм решений, представляющих булевы функции, посвящена обширная литература. Рассматривались конкретные

функции (сумматоры, умножители, пороговые функции, мультиплексеры, функцию бита скрытого веса и др.) [17-20] и произвольные функции из Р2.

Функция прямого доступа к памяти (мультиплексер), определенная для п = 2Р + р переменных, определяется следующим образом: значения первых 2Р рассматриваются как таблица истинности для подфункций от последних р переменных. Эта функция реализована во многих электронных схемах и замечательна тем, что при таком порядке переменных имеет максимальную

автоматную сложность О в Р™ [21], а при обратном - сложность (}1ЮЕШВ

0(п2) и сложность ЯОВОБ 0(п) [15,22].

Автоматная сложность класса всех булевых функций была впервые рассмотрена Кузьминым [23]. Он получил оценку функции Шеннона

2п 2п — < §(Р2п,п) < 2- — п п

и отметил, что ее график имеет пилообразный вид. Позже его результаты Кузьмина были повторены и частично уточнены. Ли [24] получил оценку для

оввв

1 2п 2п

-■ — + 1 < §0ВШ)(Р2п,п) <4---2

I п п

Ляу и Линь [25], Брейтварт, Хант и Розенкранц [26] довели оценку до результата Кузьмина. Хип и Мерсер [27] получили формулу для максимальной сложности ЯОВБО

*яовоо(Гг>п) = 2П_Р - 22Р - 3

и отметили осцилляции графика функции Шеннона. Шампорно и Пен [28] получили (в терминах конечных автоматов) ту же оценку функции Шеннона для Р2 и привели формулу

V

§(Р2п,п) = 2п~р - р - 2 + ^ 22\

/=о

где величина р определяется через обращение функции п(х) = 2х + х или сравнение величин 2n~q и 224. В этой статье введена константа автоматной сложности для класса Р2, понимаемая как предел величины п • п)/2п.

Более детально функция Шеннона класса Р2 была исследована Грёплем [14,29,30]. Он описал поведение ее графика вблизи особых точек вида п = 2Р + р (вершин «зубцов» графика) и привел асимптотические оценки и точные формулы максимальной сложности QROBDD и ROBDD. Для нахождения параметра р, входящего в состав формул, используется функция L{n) = п + log п и ее оценки или сравнение величин 2n~q и 2гЧ. В работе Мишона, Юнеса и Валаршера [21] введено понятие сложной функции из Р2 (имеющей QROBDD максимальной сложности), приведена диаграмма решений сложной функции и рассмотрены некоторые свойства и метрические характеристики сложных функций.

Сложность упорядоченных Агарных диаграмм решений для М-значных функций, рассматривалась Дворжаком [31]. Он получил формулу для сложности таких ROBDD

Nn-P _ г

N- 1

+ MNP - М,

возможно, содержащую неточность, и значения сложности для малого числа переменных.

В работе Грубера и Хольцера [32] исследовалась средняя сложность детерминированных и недетерминированных автоматов, представляющих конечные языки длины не больше п в алфавите мощности к. Ими была получена оценка максимальной сложности автомата 0(/сп/п). В работе Кампяну и Хо [33] были получены формулы максимальной сложности конечных автоматов, представляющих конечные языки длины п и длины не больше п. Формула для языков не больше п имеет вид

дГП-р+1 _ ^ /уР-дг

N-1

но величина р вычисляется иначе, чем в данной работе, в силу отличий в определении автомата-акцептора. Сложность классов конечных языков длины, равной мощности входного алфавита, рассматривалась в статье Бржозовски и Константинидиса [34].

Значимых результатов для автоматной сложности других классов Поста, в частности, для замкнутых классов монотонных функций до сих пор не получено.

В данной диссертации предложен ряд методов синтеза сложных автоматов, представляющих булевы функции. С их помощью построены автоматы максимальной или асимптотически максимальной сложности, представляющие функции из различных классов Поста, в том числе из замкнутых классов монотонных функций. Приведены точные формулы и асимптотические оценки функции Шеннона для классов Поста. В соответствии с полученными результатами классы решетки Поста разбиваются на 3 группы в соответствии с асимптотическим поведением функции Шеннона их автоматной сложности.

В диссертации рассматривается также автоматная сложность конечных языков, состоящих из слов длины п (такие языки соответствуют М-значным функциям) и языков длины не больше п. Для этих классов языков получены точные формулы и асимптотические оценки функции Шеннона.

Рассмотрена также связь автоматной сложности классов Поста со сложностью классов в других моделях и показано, что автоматная сложность является независимой характеристикой класса и не сводится к другим мерам сложности.

Основные результаты диссертации опубликованы в [35-43].

§ 2. Основные понятия и обозначения

Пусть А, В, - конечные алфавиты, |Л| = N > 2, \В\ = М > 2. Не ограничивая общности, можем считать, что А = {ОД,... N — 1}, В = {ОД,... М — 1}. Конечный алфавит мощности 2 будем обозначать через Е = {ОД}. Наборы из п элементов алфавита А можно рассматривать как слова

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

Конечным языком Ь в алфавите А назовем любое непустое конечное подмножество Ь с А*. Множество языков в алфавите А обозначим через £(А).

М-коллекцией языков С из множества % £ назовем семейство попарно не пересекающихся языков {Ь1,... Ьм_1) Я К. Множество М-коллекций языков из % обозначим через См {К). Для М-коллекции С языков из % будем считать, что Ь0 = 0С\ II ¿^х1

Определим детерминированный конечный автомат (ДКА) и инициальный конечный автомат (ИКА) согласно [7].

Конечным автоматом назовем набор У = (А, В, (р, хр), где (р\ х А -» $ - функция переходов, тр\ @ х А В - функция выходов.

Инициальным конечным автоматом (ИКА) УЯо назовем конечный автомат У с выделенным начальным состоянием Удо = (А,В,(},(р, гр, д0).

ИКА УЧо = (А,В,(},(р,-ф,цо) представляет язык I с А* с помощью подмножества выходных символов В' £ В, если а Е Ь <=> \pCqo, а) е В этом случае говорим также, что язык Ь представим в автомате Уд с помощью В'. Обозначим представимость языка I в автомате УЧо через Уд Не ограничивая общности, считаем, что В' = #\{0}.

ИКА Удо = (А, В, (р, тр, qQ) представляет М-коллекцию языков

С £ £(А), если V а Е г = 0,... М — 1 выполнено = г- В этом случае

говорим также, что коллекция С представима в автомате УЯо. Представимость коллекции С в автомате УЯо обозначим через УЯо~С.

Обозначим через Ап = {а Е А*\\а\ = п] множество слов длины п и через А~п = {а 6 Л*||а| < п} - множество слов длины не более п в алфавите А. Положим £п(А) = {ЬЕ £(А)}1 Е А71} и £*(А) = {Ь Е £{А)\I с А*п). Для множества языков % £ £{А) обозначим %{п) = X П £п{А) и ЭС-(п) = К П £п(А).

Сложностью §(Vq) автомата Vq назовем |(?| - число состояний в автомате Vq. Сложностью языка L 6 L(Ä) назовем величину §(L) = min S(V^).

Vq~L

Сложностью М-коллекции С Q £(Ä) назовем величину §(С) = min S(V^)

vq~c

Функциями Шеннона множества % Q £(Á) назовем величины §(%п)= max §(L), %-(ЗС,п) = max §(L),

LSJC(tí) L€JC~(TI)

W*.») = e6cmax(n))S(C), S%,M(X,n) = сесшÍM)S(C).

Множество An можно рассматривать как и-мерный N-значный куб Ап = А х ... х А. Через Еп будем обозначать «-мерный двоичный куб. Через обозначим множество М-значных функций, определенных на Ап, Р£м = {f\f: Ап В} и положим PNM = Un>o Рn,m• Через Р™ обозначим множество всех булевых функций от п переменных и положим Р2 = Unao^5"- Если К Q PN M {К с р2)} положим Ж(п) = ЗС П Р£м (JC П Р2П).

Существует взаимно-однозначное соответствие между языками из Хп(£") и функциями из Р", определяемое условием а. 6 L <=> /(а) = 1. Будем говорить, что в этом случае язык L соответствует функции /, L~f. Будем считать, что автомат VqQ, представляющий язык L е Ln(E), представляет и соответствующую ему функцию / G Р" - Vq0~f-

Назовем сложностью §(/) булевой функции / сложность §(L) языка L, L~f. Функцией Шеннона множества булевых функций ОС Я Р£ назовем

величину SCK.ri) = max §(L).

L~fjex(n)

Аналогично определяется взаимно-однозначное соответствие между М-коллекциями из СМ(£П(Л)) и функциями из РДМ: йё L¿ <=> /(а) = í, i = 0,... М — 1. В этом случае коллекция С соответствует функции /, C~f. Будем считать, что автомат Vqo, представляющий коллекцию С £ См(£П(Л)), представляет и соответствующую ей функцию / е PftM - Vqo~f.

Назовем сложностью §(/) функции / £ сложность 2 (С) М-

коллекции С, С~/. Функцией Шеннона множества функций X £ РДМ назовем

величину Зд^СЗСп) = шах 2(С).

с~/,/езс(п)

§ 3. Основные результаты

Диссертация состоит из введения, четырех глав, заключения, трех приложений, списка рисунков и списка литературы, содержащего 61 наименование.

В Главе 1 рассматриваются методы построения сложных автоматов, представляющих конечные языки, коллекции языков и функции. Общий подход к синтезу автоматов заключается в построении диаграммы автомата путем объединения прямого и обратного деревьев. Выбор деревьев и способов их объединения позволяет получить автоматы для языков и функций из различных классов.

Разработан оригинальный метод синтеза сложных автоматов, представляющих монотонные функции. Для этого используется специальное отображение единичного куба в множество монотонных булевых функций, названное монотонным вложением.

Найден простой способ вычисления параметра р (высоты обратного дерева), входящего в состав формул сложности построенных автоматов. При этом не требуется сравнение величин вида 2п-£? и 224 или обращение функций вида п{х) = 2х + х.В Приложении А приведены формулы вычисления высоты обратного дерева для построенных сложных автоматов.

В Главе 2 предложенные методы используются для оценки автоматной сложности замкнутых классов булевых функций. Приведем обозначения замкнутых классов, введенных Постом в [44,45], и их описания:

• Ср I = 1, ...4 - все булевы функции, все функции сохраняющие О и/или 1.

• А0 I = 1,... 4 - все монотонные функции, все монотонные функции сохраняющие 0 и/или 1.

• I = 1,2,3 - все самодвойственные а-функции, все монотонные самодвойственные функции, все самодвойственные функции.

• /I = 2,... оо - все а-функции, удовлетворяющие условию (а^)

• ц = 2,... оо - все монотонные а-функции, удовлетворяющие

условию

• [Л = 2,... оо - все монотонные функции, удовлетворяющие условию

• ц = 2,... оо - все функции, удовлетворяющие условию

• ¡л = 2,... оо - все а-функции, удовлетворяющие условию (Ам).

• ц = 2,... оо - все монотонные а-функции, удовлетворяющие условию (Ам).

• Е}1, ¡л = 2,... оо - все монотонные функции, удовлетворяющие условию (Ам)

• ¡1 = 2,... оо - все функции, удовлетворяющие условию (Ам).

• ¿¿, I = 1,... 5 - классы линейных функций.

• 5^, I = 1,3,5,6 - классы логических сумм.

• I = 1,3,5,6 - классы логических произведений.

• ОI, I = 1,... 9 - классы констант и/или переменных.

Вышеперечисленные классы образуют решетку Поста, приведенную в

[46].

Для классов С1, С2, С3, С4, В1,получены точные значения и асимптотика функции Шеннона, а также построены автоматы, представляющие самые сложные функции в классах. Показано, что классы У = 1,4,5,8, существенно сложнее в автоматном смысле, чем соответствующие классы

Считаем далее, что р,п £ И, положим п(р) = 2Р + р.

Теорема 2.1. Ур > 1, п £ [п(р), п(р + 1)) и X £ {С^, С2, С3, С4} существует такая функция /п £ Х(п), что

SОС, ri) = §(/n) = 2n_p - p - 2 + ^ 22'.

i—O

Теорема 2.2. Vp > 1, n G [n(p),n(p + 1)) и класса ОС G {DVD3} существует такая функция fn s G 0C(n), что

v

§(% n) = S(/n,s) = - p - 2 - u(p) + ^ 22',

i=0

m(P) = {;

где = j22 " при n = n(p) Ш иначе

Теорема 2.3. При n oo и Ж G {C1; C2, C3, C4, Dlf D3]

2n 2n — < S (JC,n) < 2 •—, n n

и при p —» oo, ?г G [n(p),n(p + 1)), n~a • 2P, or G (1,2] выполнено

2n

S (3C,ri)~a-—.

n

Теорема 2.4. Vp > 2 и ОС G {Fy00, = 1,4,5,8} существует такая функция /п оо G ЗС(п), что при n G (n(p) + l,n(p + 1) + 1)

p

3

§(JC,n) = S(/n oo) = - ■ 2n"P - p - u(y) + ^ 22',

i=0

и при 71 = n(p) + 1

V

SQC, n) = §(/П(00) = 2n"P - p - 1 - uO) + ^ 22\

[1 при у = 1,4 где um = . - D.

(2 при; = 5,8

Теорема 2.5. При n oo и К G {F/°, = 1,4,5,8}

i—O

3 2n 3 2n

4 n 2 n

и при p —> oo, n~a ■ 2P, a G (1,2], n G [n(p) + l,n(p + 1) + 1) выполнено

Теорема 2.6. Ур > 1 и % е ) — 1,4,5,8} существует такая функция /п,2 е %{п), что при п е (п(р) + 1 ,й(р + 1) + 1)

V

о

§(Х,п) > §(/п<2) = - ■ 2ГР - р - и{]) + 22Р~1 + £ 22',

1=0

[1 при / = 1,4

где- '-'л -

u(j) = £

2 при у = 5,8' и при п = п(р) + 1

р

S(%п) > §(/п,2) = 2п-Р - р - 1 + > 22'.

¿=о

Следствие 2.1. При р-»оо, n = 2p+p + l-H, ieN выполнено §(F/,n) ^ di ■ §(F/°,n) для некоторого dj > 1 и у = 1,4,5,8.

Следствие 2.2. При п -> оо и К G [Fj1,^ > 2,j = 1,4,5,8} выполнено

3 2п 2п

-• — £ §(JC,n) < 2 ■—.

4 п п

Для классов Л1( Л2, Л3, Л4, D2, F22, F32, F62, F72, F2°°, F3°°, F6°°, F7°° получены асимптотические оценки функции Шеннона и построены автоматы, представляющие сложные функции. Показано, что числовая ось, представляющая аргумент функции Шеннона (число переменных), распадается на последовательность пар интервалов, на больших из которых функция Шеннона асимптотически равна сложности построенных функций, а на меньших превосходит ее не более, чем вдвое.

Положим п(р) = (|р/2]) + р' й№ = i[p/2 + lj) + с = -Щк.

Теорема 2.7. При р -> оо, п 6 (п(р — l),n(p) + р mod 2] и % 6 {Л-l, Л2, Л3, Л4} существует такая функция дп G ЭС(п), что

Sfon) £ 2n-p+1.

Для функции выполнено

§(%n) < 2 - S(gn)

V

при n~a (|p/2j)'a e (2' n e ~ имеет место асимптотическая

и

оценка

2 ас 2п

S(5C,n)~S(<gn)~ -== ■ —.

д/logn п

Теорема 2.8. При р 00, п 6 (п(р - 1 ),п(р)] и JC е {F/,; = 2,3,6,7} существует такая функция дп 2 Е ЗС(п), что

Для функции дп2 выполнено

§(%п)<2-§(>П)2)

иприп~а ([p/2j)'а е (2' 72 е ~ 1)»й(р)] имеет место асимптотическая оценка

lac 2п

§С7С,п)~§(>П(2)<

ТУо^п и

Теорема 2.9. При р -> оо, п Е (п(р — 1) + 1 ,п(р) + 1] существует такая функция 6 О2 (п), что

Для функции дп 5 выполнено

§ф2,п) < 2 • §(дП13)

и при п~а ([р/2])' а е (2' ^ ' п е — 1) + 1'^Ср) + 1] имеет место асимптотическая оценка

2ас 2п

yiogn п

Теорема 2.10. При р -> 00, п Е (п(р — 1) + l,n(p) + 1 + р mod 2] и К G {Fj°,j = 2,3,6,7} существует такая функция дп оо Е Ж(п), что

Для функции дп оо выполнено

§(Х,п) < 2 ■ §(<7П|00)

и при п~а ([р/2])' а е (2' п С ^^ — 1) + + 1] имеет место

асимптотическая оценка

3 ас 2п

2у[\о%п п

Следствие 2.3. При р оо и К Е > 3,у = 2,3,6,7} выполнено

3 с 2П 2с 2п

-< §(% 71) <

п л^О&П 71

Далее рассматривается автоматная сложность классов Поста ц > 3. Для нетривиальных подмножеств этих классов получены нижние

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

Теорема 2.11. Чц > 3, р > 1о g(|J. - 1) и К Е ; = 1,4,5,8}

существует такая функция /п^ Е Х(п), что при п 6 (п(р) + ц — 1 ,п(р + 1) + А*)

р

11 + 1

1=0

= ■ 2*-р - р - 3 + {ц - 1) • (г2""1 + и(/)) + £ 22'

и при гг = п(р) + д — 1

р

л) = ' 2П"Р - Р " 2 + 01 - 1) ■«(/) +

¿=о

[2 при; = 1,4 где иш = с 0.

v (.1 при j = 5,8

При р-+оо,п~а-2р,аЕ [1,2], п Е (n(p) + ¡л — l,n(p + 1) + д) выполнено

/ \ ii + 1 2" §(% n) > §(/n<M, n) > а • ■ —*

при п = п(р) + [1 — 1 выполнено

Теорема 2.12. V/i > 2, р > max(logO + 1 - [log(ju + 2)J),log[log(^ + 2)J + 1), n E [n(p) +¡1 + 1- [log(¡i + 2)J, n(p + 1) + д + 1 - [logO + 2)J + p mod 2) и

i = 1,4,5,8} существует такая функция fn fl E %{п), что

\ + 2)(/i + 3) + 2 S(/„,M,nJ =-^з--2n P - p + uO,;) + ^ 2 '

i=0

(¡1-2 при j = 1,4

где иш,1) = i 0 . г о .

\r->jj (_2 при; = 5,8

При p оо, n~ a-2p, (XE [1,2], n e [n(p) + /i + 1 - [logO + 2)J,n(p + 1) + ¡i + l — [log(/i + 2)J + p mod 2) выполнено

«Zfir л > *r? \ > fr + 2)fr + 3) + 2 2n §(Jf,n)>S(/¥,n)>a--^з--—.

Теорема2.13.Приp-»oo,ц>2нЗСЕ {Fji\Fji+1, j = 2,3,6,7}существует

такая функция gnfl E K(ri), что при n ~ a ([p/2])' a e [2' и n e ^^ — +

¡1 — 2, n(p) + ¡г — 2] имеет место асимптотическая оценка

и 2 ос с 2п §(JC, n) > §(gnifl, п)>--= ■ —.

Теорема 2.14. При р-»оо, ¡¿>2, п ~ а ([р/2])' а е [2' и

п 6 (п(р - 1) + ¡i + 1 - TlogO + 2)1, п(р) +¡1+1- Rog(¡1 + 2)1] и X Е у = 2,3,6,7} существует такая функция gn fi Е К(п), что

+ 2) + 3) + 2 2ас 2П

2м+з

УГо^п я

Приведенные выше утверждения дополняет следующая Теорема 2.15, опирающаяся на известные оценки сложности [7]. Доказательство этой теоремы не приводится ввиду его простоты.

с,

ф - классы первого пояса 3 - классы второго пояса О - классы третьего пояса

Рис. 1. Разбиение решетки классов Поста в соответствии с асимптотикой автоматной сложности

Теорема 2.15. Для следующих классов достижимы точные значения автоматной сложности:

• §(/,1,п) = 2п, /=1,2,3,4,5.

• п) = 2п, ¿=1,3,5,6.

• $(^(71)) = п + 1, ¿=1,3,5,6.

• 2(0;(п)) = п + 1, ¿=1,2,4,5,6,7,8,9.

. 5(03(п)) = 1.

Таким образом, имеет место разбиение решетки классов Поста на три пояса в соответствии с асимптотикой автоматной сложности. На Рис. 1 изображена решетка Поста с поясами, обозначенными черным, серым и белым цветами.

Пусть т = {т^} - строго возрастающая последовательность, т^ оо. Если % - один из классов первого пояса Сх,Сг,Съ>^4> ,¥™ ,

__2 п

или ег0 подмножество, положим §(Х,п) = —. Если К - один из классов второго пояса Ах,Аг,Аъ, Л4, й2> ¥$, Р2, Р2, ¥?¥£, ¥7со, ,

или его подмножество, положим §(ЗС,п) = Если К - один из

классов третьего пояса, §(К,п) = п.

Назовем константой автоматной сложности последовательности функций {/¿}, fl € %{т{) и представляющих их автоматов {УЧд}, где % - класс Поста, величины

А(/;,т) = }1т=7--- и А[Уа 1,т) = Ьт^-

1 _Ь ПГ\ (К I «VI 1 ^ "' ' I _1 ГШ (Р I

(если пределы существуют). Назовем константой автоматной сложности для Ж и т, где % - класс Поста или его подмножество, величину

§(ЭС, т.)

А(0С,т) = Пт^-^

¿-»ЗС^т^

(если предел существует). В Приложениях В, С сравниваются константы автоматной сложности для классов Поста при различных значениях п.

В Главе 3 рассматриваются более сложные языки. Получены точные значения и асимптотика функции Шеннона для классов конечных языков £п(А) и £^(Л). Построены автоматы, представляющие самые сложные коллекции языков. Такие автоматы моделируют процесс выбора одного из М возможных решений при N альтернативах на каждом шаге.

Считаем далее, что М, N ЕЧ, М,Л/Г>2, |Л| = М, р,пЕЫ, положим

( ЛГР+1-/У N Р-М\

М N-1 -М N-1 ^р.

Теорема 3.1. Ур > 1, п е [Я^(М(р),Пдг(М(р + 1)) существует такая М-коллекция языков СЫ М п Е СМ(£П(Л)), что

§л,1М(£(Л),п) = §(Сд,<м,п) = §(/„,*,,„) = - Р ~ М + 1 + £

¿=о

Теорема 3.2. При р оо для функции Шеннона м верно

1оемМ Ып лг*

г' V5 (£(л)'п) 5 N-1 ■

и при п~а ■ ■ \ogff М,а Е (1, ДО], п Е (пым(р),пым(р + 1)] выполнено

а-1овд,М Nn 8^00,п)~ ^ •—.

Теорема 3.3. Ур > 1, п е (п^ м(р — существует такая

М-коллекция языков е См (¿„(Л)), что

ууП-р+1 _ ^

= §(4,М(П) = ы_г +МЫ-1.

Теорема 3.4. При р оо для функции Шеннона м верно ЛГ-к^М Ып 5 ЛР

(М -1)2 ' V ~ ~ - 1)2 " V

и при сг 6 [1,М], п е (п^мСр — 1)»йуу(м(р)] выполнено

(ЛГ - 1)2 71

В Главе 4 рассматриваются другие меры сложности булевых функций и их классов, а также их соотношение с автоматной сложностью.

Покрывающим автоматом ир для ИКА Уц, представляющего конечный язык £ £ а*, назовем автомат, представляющий (не обязательно конечный) язык

L Q A*,L П Al = L, где l = max|a| [12]. Покрывающим автоматом Uv для ИКА

аеь F

Vq, представляющего М-коллекцию языков С с £(Л), назовем автомат, представляющий М-коллекцию (не обязательно конечных) попарно не пересекающихся языков С = {L1, ...LM_1], L с Л*, ¿¿ПЛ'^!^ где I -максимальная длина слова в языках Llt... Обозначим через Up > Vq то, что автомат Up является покрывающим для ИКА Vq. ä Е Lit i = 1,... М

Список литературы диссертационного исследования кандидат наук Кибкало, Мария Александровна, 2013 год

Список литературы

Список составлен в порядке упоминания работ в тексте диссертации

1. Лупанов О.Б. О возможностях синтеза схем из разнообразных элементов. Доклады АН СССР. Т. 103, № 4, 1955, с. 561-563

2. Яблонский С.В. Основные понятия кибернетики. Проблемы кибернетики, Выпуск 2, Физматгиз, Москва, 1959, с. 7-38

3. Shannon С.Е. A Mathematical Theory of Communication, Bell System Technical /ournal, Volume 27, 1948, pp. 379-423, 623-656

4. Клини C.K. Представление событий в нервных сетях и конечных автоматах. В Шеннон К.Э., Маккарти Дж. (ред.), Автоматы, Издательство иностранной литературы, Москва, 1956, с. 15-67

5. Мур Э.Ф. Умозрительные эксперименты с последовательностными машинами. В Шеннон К.Э., Маккарти Дж. (ред.), Автоматы, Издательство иностранной литературы, Москва, 1956, с. 179-210

6. Минский М. Вычисления и автоматы, Мир, Москва, 1971

7. Кудрявцев В.Б., Алешин С.В., Подколзин A.C. Введение в теорию автоматов. Наука, Москва, 1985

8. Гилл А. Введение в теорию конечных автоматов. Мир, Москва, 1966

9. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений, Издательский дом «Вильяме», Москва, 2002

10. Yu S., Chapter 2. Regular Languages, In: Rozenberg G., Salomaa A. (eds.) Handbook of Formal Languages, Springer-Verlag, 1998, pp. 41110

11. Wegener I. The Complexity of Boolean Aunctions. John Wiley & Sons Ltd. and B.G. Teubner, Stuttgart, 1987

12. Cämpeanu C., Säntean N., S., Yu S. Minimal Cover Automata for Finite Languages, In=: Champarnaud J.-M., Maurel D., Ziadi D. eds., WIA'98, Lecture Notes in Computer Science 1660, Springer-Verlag, 1999, pp. 4356

13. Bryant R.E. Graph Based Algorithms for Boolean Functions Manipulation, IEEE Transactions on Computers, Volume C-35, Number 8, 1986, pp. 677-692

14. Gröpl С. Binary Decision Diagrams for Random Boolean Functions; Dissertation, Humboldt Universität zu Berlin, 1999

15. Wegener I. Branching Programs and Binary Decision Diagrams. Theory and Applications, SLAM Monographs on Discrete Mathematics and Applications, Philadelphia, PA, 2000

16. Champarnaud J.-M., Duchamp G., Finite Automata and Boolean Functions. Proceedings of SCI'2001 (Systemics, Cybernetics and Informatics), XIV, Orlando, FL, 2001, pp. 126-131

17. Hosaka К., Takenaga Y., Yajima S. On the Size of Ordered Binary Decision Diagrams Representing Threshold Functions, Proceedings of ISAAC'1994 (International Symposium on Algorithms and Computation), Springer-Verlag, 1994, pp. 87-93

18. Bollig B. The Optimal Read-Once Branching Program Complexity for the Direct Storage Access Function. Information Processing Letters, Volume 106, Issue 4, 2008, pp. 171-174

19. Bollig В., Range N., Wegener I. Exact OBDD Bounds for Some Fundamental Functions. Theory of Computing Systems, Volume 47, Number 2, 2010, pp. 593-609

20. Sawitzki D. Lower Bounds on the OBDD Size of Graphs of Some Popular Functions. In: Vojtâs P., Bielikovâ M., Charron-Bost В., Sykora O. (eds.): SOFSEM 2005, Lecture Notes in Computer Science 3381, Springer Verlag, 2005, pp. 298-309

21. Michon J.-F., Yunès J.-B., Valarcher P. On Maximal QROBDD of Boolean Functions. Theoretical Informatics and Applications, Volume 39, Issue 4, 2005, pp. 677-686

22. Bollig В., Lobbing M., Sauerhoff M., Wegener I. On the Complexity of the Hidden Weighted Bit Function for Various BDD Models. Theoretical Informatics and Applications, Volume 33, 1999, pp. 103-115

23. Кузьмин В.А. Реализация функций алгебры логики автоматами, нормальными алгорифмами и машинами Тьюринга. Проблемы кибернетики, Выпуск 13, Наука, Москва, 1965, с. 75-96

24. Lee C.Y. Representation of Switching Circuits by Binary Decision Programs. Bell System Technical Journal, Volume 38, 1959, pp. 985-999

25. Liaw H.-T., Lin C.-S. On the OBDD-Representation of General Boolean Functions. IEEE Transactions on Computers, Volume 41, Number 6, 1992, pp. 661-664

26. Breitbart Y., Hunt III H., Rosenkrantz D. On the Size of Binary Decision Diagrams Representing Boolean Functions, Theoretical Computer Science, Volume 145, Issue 1-2, 1995, pp. 45-69

27. Heap M.A., Mercer M.R. Least Upper Bounds on OBDD Sizes, IEEE Transactions on Computers, Volume 43, Issue 6, 1994, pp. 764-767

28. Champarnaud J.-M., Pin J.-E. A Maxmin Problem on Finite Automata. Discrete Applied Mathematics, Volume 23, Issue 1, 1989, pp. 91-96

29. Gropl C., Promel H.J., A. Srivastav. Size and Structure of Random Ordered Binary Decision Diagrams (Extended Abstract). In: Krob D., Meinel C., Morvan M. eds., STACS 98, Lecture Notes in Computer Science 1373, Springer-Verlag, 1998, pp. 238-248

30. Grôpl C., Promel HJ. and Srivastav A. On the Evolution of the Worst-Case OBDD Size, Information Processing Letters, Volume 77, Issue 1, 2001, pp. 1-7

31. Dvorak V. Bounds on the Sizes of Decision Diagrams. Journal of Universal Computer Science, Volume 3, Issue 1, 1997, pp. 2-22

32. Gruber H., Holzer M. On the Average State and Transition Complexity of Finite Languages, Theoretical Computer Science, Volume 387, Issue 2, 2007, pp. 167-176

33. Campeanu С., Ho W.H. The Maximum State Complexity for Finite Languages. Journal of Automata, Languages and Combinatorics, Volume 9, Issue 2-3, 2004, pp. 189-202

34. Brzozowski J., Konstantinidis S. State-Complexity Hierarchies of Uniform Languages of Alphabet-Size Length, Theoretical Computer Science, Volume 410, 2009, pp. 3223-3235

35. Кибкало M.A. О сложности представления коллекции языков в конечных автоматах, Интеллектуальные системы, Том 13, Выпуск 1-4, 2010, сс. 347-360

36. Кибкало М.А. Об автоматной сложности некоторых классов булевых функций, Интеллектуальные системы, Том 14, Выпуск 14, 2010, сс. 319-322.

37. Кибкало М.А. Об автоматной сложности классов Поста булевых функций, Интеллектуальные системы, Том 15, Выпуск 1-4,2011, сс. 379-400.

38. Кибкало М.А. Представление коллекций языков в конечных автоматах. Труды Международной конференции «Современные проблемы математики, механики и их приложений», посвященная 70-летию ректора МГУ академика В.А. Садовничего, секция «Интеллектуальные системы и компьютерные науки», 2009, сс. 358-359.

39. Кибкало М.А. О сложности представления коллекций языков в конечных автоматах. Материалы докладов XVI Международной конференции студентов, аспирантов и молодых ученых «Ломоносов», секция «Математика и механика», 2009, сс. 32-33.

40. Кибкало М.А. Представление коллекций языков автоматами. Материалы X международного семинара «Дискретная математика и ее приложения», Секция «Теория интеллектуальных систем и автоматов», 2010, сс. 361 - 363.

41. Кибкало М.А. Автоматная сложность классов Поста. Материалы Международного молодежного научного форума «ЛОМОНОСОВ-2011», секция «Математика и механика», подсекция «Математика», 2011.

42. Кибкало М.А. Оценки автоматной сложности классов булевых функций. Материалы X Международной конференции «Интеллектуальные системы и компьютерные науки», 2011.

43. Кибкало М.А. Об автоматной сложности некоторых классов Поста булевых функций. Материалы XI международного семинара «Дискретная математика и ее приложения», посвященного 80-летию со дня рождения академика О.Б. Лупанова, Секция «Теория интеллектуальных систем и автоматов», 2012, сс. 343-346.

44. Post E. The Two-Valued Iterative Systems of Mathematical Logic. Princeton University Press, 1941

45. Post E. Introduction to a General Theory of Elementary Propositions, American Journal of Mathematics, Volume 43, Number 1,1921, pp. 163185

46. Яблонский C.B., Гаврилов Г.П., Кудрявцев В.Б. Функции алгебры логики и классы Поста. Наука, Москва, 1966

47. Champarnaud J.-M., Michon J.-F. Automata and Binary Decision Diagrams, In: Champarnaud J.-M., Maurel D., Ziadi D. eds., WIA'98, Lecture Notes in Computer Science 1660, Springer-Verlag, 1999, pp. 178182

48. Korner H. A Time and Space Efficient Algorithm for Minimizing Cover Automata for Finite Languages, International Journal of Foundations of Computer Science, Volume 14, Issue 6, 2003, pp. 1071-1086

49. Яблонский C.B. Введение в дискретную математику. Наука, Москва, 1966

50. Коршунов А.Д. Число ¿-неразделенных семейств подмножеств п-элементного множества (¿-неразделенных булевых функций). Часть 1. Случай четных п и к = 2. Дискретный анализ и исследование операций, Серия 1, Том 10, № 4, 2003, с. 31-69

51. Коршунов А.Д. Число ¿-неразделенных семейств подмножеств п-элементного множества (¿-неразделенных булевых функций). Часть II. Случай нечетных п и к = 2. Дискретный анализ и исследование операций, Серия 1, Том 12, № 1, 2005, с. 12-70

52. Коршунов А.Д. Число ¿-неразделенных семейств подмножеств п-элементного множества (¿-неразделенных булевых функций). Часть III. Случай к > 3 и произвольных п. Дискретный анализ и исследование операций, Серия 1, Том 12, № 3, 2005, с. 60-73

53. Коршунов А.Д. О мощности и структуре некоторых замкнутых классов Поста (семейств подмножеств конечного множества), Модели и методы оптимизации, Наука, Новосибирск, 1988, с. 159204

54. Коршунов А.Д. О числе и строении монотонных булевых функций. В: Лупанов О.Б. (ред.) Дискретная математика и ее приложения: Сборник лекций молодежных научных школ по дискретной математике и ее приложениям. Часть 1, МГУ им. М.В. Ломоносова, Механико-математический факультет, Москва, 2001, с. 34-58

55. Сапоженко А.А. О числе антицепей в многослойных ранжированных множествах, Дискретная математика, 1989, Том 1, Выпуск 2, с. 110-128

56. Емеличев А.В., Сапоженко А.А. О числе монотонных самодвойственных функций. Материалы Второго Всесоюзного семинара по дискретной математике и ее приложениям. Издательство МГУ, Москва, 1988, с. 140-141

57. Лупанов О.Б. Об одном методе синтеза схем. Известия вузов. Радиофизика, 1, 1958, с. 120-140

58. Угольников А.Б. О реализации функций из замкнутых классов схемами из функциональных элементов. Математические вопросы кибернетики, Выпуск 1, Москва, Наука, 1988, с. 89-113

59. Угольников А.Б. О реализации монотонных функций схемами из функциональных элементов. Проблемы кибернетики, Выпуск 32, Москва, Наука, 1976, с. 167-185

60. Ансель Ж. О числе монотонных булевых функций от п переменных, Кибернетический сборник, Новая серия, Выпуск 5, Мир, Москва, 1968, с. 53-57

61. Campeanu С., Paun S., Yu S. An Efficient Algorithm for Constructing Minimal Cover Automata for Finite languages, International Journal of Foundations of Computer Science, Volume 13, Issue 1, 2002, pp. 83-97