автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Автоматная сложность булевых функций из классов Поста

ФГБОУ ВПО Московский государственный университет имени М.В. Ломоносова

На правах рукописи

КИБКАЛО Мария Александровна

Автоматная сложность булевых функций из классов Поста

Специальность 05.13.17 - теоретические основы информатики

АВТОРЕФЕРАТ 5 ДЕК 2013

диссертации на соискание ученой степени кандидата физико-математических наук

Москва-2013

005542441

005542441

Работа выполнена на кафедре математической теории интеллектуальных систем механико-математического факультета ФГБОУ ВПО «Московский государственный университет имени М.В. Ломоносова».

Научный руководитель: доктор физико-математических наук,

профессор Бабин Дмитрий Николаевич

Официальные оппоненты: доктор физико-математических наук,

профессор Чечкин Александр Витальевич ФГВОУ ВПО «Военная академия Ракетных войск стратегического назначения имени Петра Великого»

кандидат физико-математических наук, ведущий инженер Зайцев Денис Владимирович ООО «ЭЛ ЭС АЙ Интернешнел Ресерч»

Ведущая организация: ФГБОУ ВПО «Российский государственный

гуманитарный университет»

Защита диссертации состоится 25 декабря 2013 года в 16 час. 45 мин. на заседании диссертационного совета Д 501.002.16, созданного на базе ФГБОУ ВПО «Московский государственный университет имени М.В. Ломоносова», по адресу: 119991, Москва, ГСП-1, Ленинские горы, д.1, ФГБОУ ВПО МГУ имени М.В. Ломоносова, механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в Фундаментальной библиотеке ФГБОУ ВПО «Московский государственный университет имени М.В. Ломоносова» (Москва, Ломоносовский проспект, д.27, сектор А, 8 этаж).

Автореферат разослан 25 ноября 2013 г.

Ученый секретарь диссертационного совета Д.501.002.16, созданного на базе ФГБОУ ВПО МГУ, доктор физико-математических наук, профессор

/

А.А.Корнев

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

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

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

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

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

1 Лупанов О.Б. О возможностях синтеза схем из разнообразных элементов. Докл. АН СССР. Т. 103, № 4, 1955, с. 561-563 1 Яблонский C.B., Гаврилов Г.П., Кудрявцев В.Б. Функции алгебры логики и классы Поста. Наука, Москва, 1966

1

Понятие конечного автомата окончательно сформировалось в результате исследования дискретных преобразователей информации3,4,5'6'7,8 и оценки их сложности (например, времени работы, числа операций для построения автомата или числа состояний автомата)9'10'11'12'. В настоящей работе под сложностью автомата понимается число его состояний.

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

Для представления функций часто используются упрощенные модели конечных автоматов — двоичные диаграммы решений (Binary Decision Diagrams - BDD), впервые примененные Брайантом13. Обзор свойств и особенностей различных видов BDD дан в диссертации Трепля14. Такой способ отличается от представления функций конечными автоматами лишь несущественными деталями15,16.

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

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

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

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

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

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

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

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

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

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

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

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

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 1. Branching Programs and Binary Decision Diagrams. Theory and Applications, SIAM 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,1819,20. Наибольший интерес исследователей вызвала функция прямого доступа к памяти (мультиплексор). Эта функция реализована во многих электронных схемах и замечательна тем, что при прямом

0 (—) 21

порядке переменных имеет максимальную автоматную сложность V« / , а при

обратном - сложность ОСп2) 22-п.

Автоматная сложность класса всех булевых функций была впервые рассмотрена А.Д. Кузьминым24. Он получил для нее оценку функции Шеннона и отметил, что ее график имеет пилообразный вид:

7П on

-^S(P2ln)<2'-п 4 " п

Позже результаты Кузьмина были повторены и уточнены25'26,27. Хип и Мерсер28 получили формулу для максимальной сложности ROBDD

S*0BDD(P2.n) = 2n-P + 22P -3 и отметили осцилляции графика функции Шеннона. Шампорно и Пен29 получили (в терминах конечных автоматов) ту же оценку функции Шеннона для Р2 и привели формулу

р

S(P2,ti) = 2П"Р - р - 2 + JV,

¿=о

" 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 11 Sawitzkj D. Lower Bounds on the OBDD Size of Graphs of Some Popular Functions. In: VojtâSP., BielikovâM., Charron-Bost В.,

Sykora О. (eds.): SOFSEM 2005, Lecture Notes in Computer Science 3381, Springer Verlag, 2005, pp. 298-309

19 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 30 Bollig В., Range N.. Wegener I. Exact OBDD Bounds for Some Fundamental Functions. Theoiy of Computing Systems, Volume

47, Number 2, 2010, pp. 593-609

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

21 Wegener I. Branching Programs and Binary Decision Diagrams. Theoiy and Applications, SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, PA, 2000 21 Bollig В.. Lobbing M.. SauerhoffM., 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

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

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

16 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

27 Breitbart Y„ Hunt III H., Rosenkrantz D. On the Size of Binaiy Decision Diagrams Representing Boolean Functions, Theoretical

Computer Science, Volume 145, Issue 1-2, 1995, pp. 45-69 21 Heap M.A., Mercer M R. Least Upper Bounds on OBDD Sizes, IEEE Transactions on Computers, Volume 43, Issue 6, 1994, pp. 764-767

29 Champamaud J.-M., Pin 1-Е. A Maxmin Problem on Finite Automata. Discrete Applied Mathematics, Volume 23, Issue 1, 1989, pp. 91-96

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

Сложность упорядоченных Агарных диаграмм решений для М-значных функций, рассматривалась Дворжаком34. В работе Грубера и Хольцера35 исследовалась средняя сложность детерминированных и недетерминированных автоматов, представляющих конечные языки. Сложность классов конечных языков длины, равной мощности входного алфавита, рассматривалась в статье Бржозовски и Константинидиса36.

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

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

Методы исследования. В диссертации используются методы дискретной математики, теории автоматов и теории синтеза и сложности управляющих систем.

30 Gröpl C., Prömel H.J.. A. Srivastav. Size and Structure of Random Ordered Binary Decision Diagrams (Extended Abstract). In: Krob D„ Meinel C„ MorvanM. eds., STACS 98, Lecture Notes in Computer Science 1373, Springer-Verlag, 1998, pp. 238-248

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

32 Gröpl C., Prömel H.J. and Srivastav A. On the Evolution of the Worst-Case OBDD Size, Information Processing Letters, Volume 77, Issue 1,2001, pp. 1-7

33 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

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

35 Gmber H., Hölzer M. On the Average State and Transition Complexity of Finite Languages, Theoretical Computer Science, Volume 387, Issue 2,2007, pp. 167-176

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

Научная новизна.

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

• Построены автоматы максимальной или асимптотически максимальной сложности, представляющие функции из классов Поста Су, А¡, й], И" для всех у к = 2,3,6,7. Получены точные формулы и/или асимптотика функции Шеннона для классов Поста. Согласно полученным результатам классы решетки Поста разбиваются на 3 группы в соответствии с асимптотическим поведением функции Шеннона.

• Для оставшихся классов Поста построены функции, автоматная сложность которых по прядку совпадает с асимптотикой функции Шеннона.

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

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

Работа имеет теоретический характер. Ее результаты могут быть полезны специалистам-исследователям Московского государственного университета им. М. В. Ломоносова, Института прикладной математики им. М. В. Келдыша РАН, Вычислительного центра им. А. А. Дородницына РАН, Института математики им. С. Л. Соболева СО РАН, Нижегородского государственного университета им. М. В. Лобачевского, Новосибирского государственного университета, Санкт-Петербургского государственного университета.

Практическая значимость.

Полученные в настоящей работе оценки показывают, что сложность программной реализации произвольной булевой функции от 50 переменных автоматами потребует 17 терабайт памяти, или микросхему, состоящую из 17 ■ 1012 логических элементов. Если при этом функция монотонна, то потребуется в худшем случае автомат с тремя терабайтами памяти, или микросхема из 2.5х1012 логических элементов. Это обстоятельство означает, что время широкого использования произвольных булевых функций в задачах кодирования и распознавания еще не наступило. В настоящем проще и дешевле применять методы, близкие к линейным. Вместе с тем, когда память в 1000 терабайт станет доступна, эти подходы станут реализуемы на практике.

5

Из утверждения 3.24 главы 3 следует, что вычислять булевы функций лучше параллельно. При этом одновременное вычисление М булевых функций увеличит память всего в log М раз, а не в М раз, как это может показаться. Дело в том, что автоматы сложных булевых функций ведут себя одинаково, отличаясь лишь на небольшом заключительном участке диаграммы.

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

С учетом представленных выше соображений результаты, представленные в диссертации, имеют важное прикладное значение.

Апробация работы. Результаты диссертации докладывались на семинарах механико-математического факультета МГУ им. М.В. Ломоносова: на семинаре «Теория автоматов» под руководством д.ф.-м.н., профессора В.Б. Кудрявцева, на семинаре «Приложения дискретных функций» под руководством д.ф.-м.н., профессора Д.Н. Бабина, а также на следующих конференциях:

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

2. XVI Международная конференция студентов, аспирантов и молодых ученых «Ломоносов», 13-18 апреля 2009 г.

3. X международный научный семинар «Дискретная математика и ее приложения», 1-6 февраля 2010 г.

4. Научная конференция «Ломоносовские чтения», 16-25 апреля 2010 г.

5. Международный молодежный научный форум «ЛОМОНОСОВ-2011», 11-15 апреля 2011 г.

6. Научная конференция «Ломоносовские чтения», 11-25 ноября 2011 г.

7. X Международная конференция «Интеллектуальные системы и компьютерные науки», 5-10 декабря 2011 г.

8. XI международный семинар «Дискретная математика и ее приложения», посвященный 80-летию со дня рождения академика О.Б. Лупанова, 18-23 июня 2012 г.

9. Международный молодежный научный форум «ЛОМОНОСОВ-2013», 8-13 апреля 2013 г.

Результаты, выносимые на защиту.

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

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

3. Точные формулы и асимптотики функции Шеннона для классов Поста.

4. Сравнение функций Шеннона автоматной сложности классов Поста с функциями Шеннона этих же классов для других моделей управляющих систем.

5. Несводимость автоматной сложности булевых функций к другим мерам сложности булевых функций.

Публикации. Основное содержание диссертации опубликовано в 9 работах автора, список которых приведен в конце автореферата [1-9].

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

Краткое содержание работы.

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

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

М-коллекцией языков С из множества К £ L(Á) назовем семейство попарно не пересекающихся языков {L1(... LM_Е К. Множество М-коллекций языков из К обозначим через См (X). Для М-коллекции С языков из ОС будем считать, что

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

V = (A,B,Q,(p,xl>),

где (р\Q х А -* Q — функция переходов, ip:Q х А -* В — функция выходов. Инициальным конечным автоматом (ИКА) Vqo назовем конечный автомат V с выделенным начальным состоянием q0: Vqo = (А, В, Q, <р, гр, q0).

ИКА Vqo = (А, В, Q, <р, ip, qo) представляет язык Z, £ Л* с помощью подмножества выходных символов В' £ В, если aEL<=> >//(q0, a) 6 В'. В этом случае говорим также, что язык L представим в автомате Vqo с помощью В'. Обозначим представимость языка L в автомате Vq¡¡ через Vqo~L. Не ограничивая общности, считаем, что В' = В\{0}.

ИКА Vqg = (Л, В, Q, <р, i¡j, <7о) представляет Л/-коллекцию языков С £ £(Л), если V a £ Lít i = О, ...М — 1 выполнено tp(q0,a) = i. В этом случае говорим также, что коллекция С пред ставима в автомате Vqo. Представимость коллекции С в автомате Vqo обозначим через Vqg~C.

Обозначим через Ап = {a е Л*||а| = п} множество слов длины п и через i4sn = {a G Л*||а| < п} — множество слов длины не более п в алфавите А. Положим £„(Л) = {L Е £(Л)|/, £ А71} и £*(Л) = [L 6 £(Л)|1. £ Л£п}. Для множества языков ЗС £ £(Л) обозначим %{п) — К Л £„(Л) и 3Cs(n) = ОС П

Жл).

Сложностью S(l^) автомата Vq назовем |Q| — число состояний в автомате Vq. Сложностью языка L £ £(Л) назовем величину

§(L) = min S(Vq)

Сложностью М-коллекции С £ £(Л) назовем величину S(C) = minS(K4)

Vq~L

Функциями Шеннона множества X £ £(Л) назовем величины §(Х,п) = шах §(/.), Ss(pC,n) = шах §(L),

4 J L€X(n) v J v ' LexHn)

W*.») = ее-(ах(п))§(е}> SfoC*.») = eeemax(n))S(0.

Множество An можно рассматривать как «-мерный íV-значный куб Л™ = Л X ... X Л. Через Еп будем обозначать и-мерный двоичный куб. Через

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

8

обозначим множество М-значных функций, определенных на Ап, РЦМ = {f\f^. Ап -* В} и положим Ры м = иП£0 Ры.м- Через Р" обозначим множество всех булевых функций от п переменных и положим Р2 = ип>о Рг- Если К £ (:К £ Р2), положим ЗС(п) =ХГ\ (К П Р£).

Существует взаимно-однозначное соответствие между языками из £„(Е~) и функциями из Р" > определяемое условием I,« /(а) = 1. Будем говорить, что в этом случае язык I соответствует функции f, L~f. Будем считать, что автомат Удо, представляющий язык Ь € £П(Е), представляет и соответствующую ему функцию / е Я2" - УЧо

Назовем сложностью §(/) булевой функции / сложность §(/,) языка I,

Функцией Шеннона множества булевых функций "К £ Р" назовем величину §(Х,п) = ^ ^тах^ Аналогично определяется взаимно-

однозначное соответствие между М-коллекциями из СМ(£П(Л)) и функциями из Р£,м: а €¿¡<=>/(5) = /, I = 0,... М — 1. В этом случае коллекция С соответствует функции /, С~/. Будем считать, что автомат представляющий коллекцию С 6 См (£П(Л)), представляет и соответствующую ей функцию / е

Назовем сложностью §(/) функции f Е Р$м сложность §(С) М-коллекции С, C~f. Функцией Шеннона множества функций К Е Р$м назовем величину $ц1М(К,п) = та

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

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

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

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

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

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

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

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

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

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

• F^, ц = 2,... оо — все функции, удовлетворяющие условию (а1*).

• [г = 2,... оо — все а-функции, удовлетворяющие условию (А*1).

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

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

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

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

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

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

• Ot, i = 1,... 9 — классы констант и/или переменных. Вышеперечисленные классы образуют решетку Поста40.

Для классов Си С2, С3, С4, Dlt D3, F™, F4°°, Fg00, Р8°°получены точные значения и асимптотика функции Шеннона, а также построены автоматы,

38 Post Е. Two-valued Iterative Systems. Princeton University Press, 1941

39 Post E. Introduction to a Genera! Theory of Elementary Propositions, American Journal of Mathematics, Volume 43, Number 1, 1921, pp. 163-185

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

10

представляющие самые сложные функции в классах. Показано, что классы Ff, j = 1,4,5,8, существенно сложнее в автоматном смысле, чем соответствующие классы Ff°.Считаем далее, что р,п £ М, положим п(р) =2р + р.

Теорема 2.1. Vp > 1, п е [n(p), n(p + 1)) и X е {Cv С2, С3, С4} существует такая функция fn £ X(ri), что

р

§(ЗД = §(/„) = 2п~р + £ 22'.

i=o

Теорема 2.2. Vp > 1, п В [n(p),n(p +1)) и класса X€{DVD3} существует такая функция £ Х(п), что

v

%(Х,п) = §(/n,s) = 2"-р - р - 2 - и(р) + Л 22',

u(p) = (о

1=0

2Р"1-!

где ulpj = i22"" при n = n(p) иначе

Теорема 2.3. При п -* оо и X Е {Сх, С2, С3, С4, Dv D3}

2n 2n — <§(?C,n)<2—, n n

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

2"

§(X,ri)~a ■ —

Теорема 2.4. Vp > 2 и X 6 j = 1,4,5,8} существует такая функция /„,«, £ ЗС(п), что при п 6 (п(р) + 1, п(р + 1) + 1)

v

SQC, n) = S(/n>00) = | • 2П_Р - р - uÜ) + 2 22',

¡=0

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

v

S(X, п) = §(/„,„) = 2П"Р - р - 1 - и(/) + £ 22',

[1 при; = 1,4 где u(j) = |2 приу = 5,8-

¡=о

и

Теорема 2.5. При п -* оо и X 6 {F/°, = 1,4,5,8}

3 2" , ч 3 2" ---<SОС.п)

4 п 2 п

и при р —> оо, п~а ■ 2Р, а £ (1,2], n £ [n(p) + l,n(p + 1) + 1) выполнено

, . За 2"

S(3C,n)~— — 4 п

Теорема 2.6. Vp > 1 и X £ {Fy2, 7 = 1,4,5,8} существует такая функция /п2 е ЗС(п), что при тг 6 (Я(р) + l,n(p + 1) + 1)

р

§(#, тг) > S(/„,2) = | ■ 2л-р - р - uQ) + 22""1 + £ 22',

1=0

... (1 приj = 1,4 ~г \ , ,

где uQ) = (2 при j = 5,8' и ПРип = n(p) + 1

р

S0C, п) > §(/„,2) = 2""Р - р - 1 + £ 22'

¡=о

Следствие 2.1. При р -> 00, п = 2Р + р + 1 + i, i £ N выполнено §(F/,n) > dj ■ §(F/°,ti) для некоторого ci( > 1 и; = 1,4,5,8.

Следствие 2.2. При п -» оо и X £ {F^, ц > 2,j = 1,4,5,8} выполнено

3 2" 2" ---SS(5C,n) < 2--

4 п п

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

Положим n(p) = (|p/2j) + Р' Й(Р) = (lp/2 + 1]) + Р' с =

Теорема 2.7. При р -» со, п £ (п(р - 1), п(р) + р mod 2] и К £ {Л1,Л2,Л3, Л4} существует такая функция дп £ Х(п), что

SCfl„) £ 2n-p+1

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

S(3f,n) < 2 ■ SCfl»)

и при n~a ([p/2j)'a e (2 ' n e ^(P — "Cp)1 имеет место асимптотическая оценка

2 ас 2"

§CK,n)~§(<7n)~

Vlogn 71

Теорема 2.8. При р п £ (п(р — 1),й(р)] и ЗС е {F/,/ = 2,3,6,7} существует такая функция дп2 G К(п), что

* 2n_p+1

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

S(Х.п) £ 2 • S(дп,2)

и при п~а а е (г'*]'п £ ("(Р — 1), п(р)] имеет место асимптотическая

оценка

2ас 2"

S(?C,7i)~S(5n,2)~

•y/logn n

Теорема 2.9. При р -» 00, ne (п(р - 1) + 1 ,n(p) + 1] существует такая функция ^„ s е D2(n), что

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

§(D2,n) 5 2 • §(5n,s)

и при п~а а G (2' п £ ^^ ~ 1) + 1.й(р) + 1] имеет место

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

2 ас 2П

S(D2, n)~S(5n,s)~-== ■ — Vlogi 71

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

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

§(ЗС,п) < 2 ■ §(дП1Са)

и при п~а ^(г'1]' 71 е (^Ср — 1) + 1, Я(р) + 1] имеет место

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

3 ас 2п

2фо%п п

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

Зс 2" 2с 2"

■ — <§СК:,71)

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

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

Теорема 2.11. \/Ц> 3, р > 1о§0 - 1) и ЗСе {р/\р/+\ У = 1,4,5,8} существует такая функция ^ е К(п), что при п £ (п(р) + (I - 1,п(р + 1) +

V

") = :^'■ 2П_Р - Р - 3 + (м - 1) ■ (22""1 + и(0) + X 22'<

¡=о

и при п = п(р) + Ц — 1:

р

Kfn*. п) = • 2П-Р - р - 2 + {¡I - 1) • u(/) + ^ 22',

i=o

(2 при j = 1,4 где = ]л npHy = 5i8-

!«0) = {1

При р-*оо,п~а-2р,ае [1,2], n G (п(р) +ц — 1, п(р + 1) + ¡г) выполнено

л ц + 1 2п §(Х, n) S §(/„,„, n) > а • • —,

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

Теорема 2.12.

Чц>2,p> max(log(At + 1 - [login + 2)J).logllog(/i + 2) J + 1), n G [n(p) + Ц + 1- LlogOz + 2)J,n(p + 1) + n + 1 - LlogO + 2)J + p mod 2) и К £ i = 1,4,5,8} существует такая функция /П|Ц е что

SVn* ») = (M + 2)2tt3) + 2 ■ - р + + Z

i=o

Г^-2 при; = 1,4 где u(jx,j) = |_2 при/ = 5(8-

При р -» оо, 7i ~ а • 2Р, а G [1,2],

тг е [п(р) + /х + 1 — [logOx 4- 2)J, n(p + 1) + ц + 1 - LlogQ* + 2)J + p mod 2) выполнено

(jt + 2)0x + 3) + 2 2"

S(K,n) > §(/„.д,п) > а ■

2"+3 n

Теорема 2.13. При р-*оо,^>2иЗСе {F/\F/+1, 7 = 2,3,6,7} существует такая функция 0njl G ЗС(гг), что при л ~ a ([J/2\)> яе[|'1]ипе ("(Р - 1) + /х — 2,п(р) + ц — 2] имеет место асимптотическая оценка

и 2 ссс 2"

Теорема 2.14. При р-»оо, ц>2,п~а ([р/2])' а е [2' и п 6 (Й(р - 1) + И- + 1 - flogOi + 2)1, п(р) +ц+1- flogCfi + 2)1] и Ж 6 {Fj'\Fj'+1, j = 2,3,6,7} существует такая функция д е 5С(п), что

. . {¡1 + 2~)(р. + 3) + 2 2ас 2" -

8(Я\n) > S(gn:lvп) S ^-^рН--уЩ^ • —' с =

Приведенные выше утверждения суммирует Теорема 2.15, опирающаяся на известные оценки сложности41.

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

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

15

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

• §($,п) = 2п, 1=1,3,5,6.

• §(Р,(п))=п +1,1=1,3,5,6.

• 2(Ог(п)) = п + 1, £=1,2,4,5,6,7,8,9. . §(03(п)) = 1.

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

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

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

сложности

Пусть т = {?П;} — строго возрастающая последовательность, т; -» оо.Если К — один из классов первого пояса С1( С2, С3, С4,03,Р™,Р™,

_ 2П

Р4М, Р^1, или его подмножество, положим §(ЗС, л) = —. Если X - один из классов второго пояса Ах, Аг, А3, А4,02, Рз> Рз°Рб°-

РЦ'.Р? или его подмножество, положим §(Х,п) = • —. Если X - один из

° ' ^10271 71

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

Назовем константой автоматной сложности последовательности функций [fi), fi е ЗС(?П[) и представляющих их автоматов [Vq ¡}, где X - класс Поста, величины

&(fi,m) = lim ——— и AfV^m) = lim- v ,

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

А (Х,т) = lim -Л

§(Х, гп;)

(если предел существует).

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

Считаем далее, что Af.WeN, M,N >2, |Л| = N, p,n е N, положим

(NP+1-N NP-N\

М Л/-1

Теорема 3.1. Vp > 1, n G [nNM(p),nNM(p + 1)) существует такая М-коллекция языков CNM n & СМ(£П(Л)), что

VmCcOO. n) = s(cWfM>n) = §(/w,M,n) == -P-M +1 + 2 MNi.

i=о

Теорема 3.2. При p -> oo для функции Шеннона SW M верно logwAf Nn , , . . W ■ logw M Nn

и при n~a • Np ■ logNM, а € (1,N], n 6 (nNM(p),nNM(p + 1)] выполнено

а ■ Iogw M Nn

W- 1

•Теорема 3.3. Vp > 1, n 6 (nNM(p — 1),йм м(р)] существует такая M-коллекция языков CNM,n е СМ(£^(Л)), что

yyn-p+1 _ I NP_N

S%#(£(.A),n) = §(CW,M,„) = дг_1 + M "-1

Теорема 3.4. При p-* °° для функции Шеннона Sjy м верно AMog„M Af"^ МЧо^МГ

W=TF' "ñ" * C£ W).») á (jV_1)2 • v

и при а € [1, W], n e (nNM(p - l),nW M(p)] выполнено

. , , ч ч а W • logw M 1Vn

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

Покрывающим автоматом Up для ИКА Vq, представляющего конечный язык L Е А", назовем автомат, представляющий (не обязательно конечный) язык

I с А\ I П А1 = L, где I = max|ä|42.

aeL

Покрывающим автоматом Up для ИКА Vq, представляющего М-коллекцию языков С Е £(Л), назовем автомат, представляющий А/-коллекцию (не обязательно конечных) попарно не пересекающихся языков С = {Lu... LM_1], L £А', Li П Л' = Li, где l — максимальная длина слова в языках Lx,... LM_t. Обозначим через Up > Vq то, что автомат Up является покрывающим для ИКА Vq. й е Li, i = 1,... М.

Сложностью покрытия автомата Vq назовем величину S>(l^() = min S(í/p). Сложностью покрытия языка L £ £(Л) назовем величину S>(¿) =

Up^Vq

min Сложностью покрытия М-коллекции С с L(Ä) назовем величину

Vq~*L

§>(С) = min S>(l{(). Сложностью покрытия §*(/) функции / из Р" или считаем сложность покрытия соответствующего языка или коллекции.

41 Câmpeanu C., Sântean N.. S., Yu S. Minimal Cover Automata for Finite Languages, In: Champamaud J.-M., Maurel D., Ziadi D. eds., WIA'98, Lecture Notes in Computer Science 1660, Springer-Verlag, 1999, pp. 43-56

18

Было показано43'44,45'46, что для некоторых языков можно построить покрывающие автоматы значительно меньшей сложности, чем автоматы, представляющие эти языки. Однако, для сложных функций из теорем Главы 2 и сложных коллекций из теорем Главы 3 это не так:

Теорема 4.1. Для функции

,s* fn,2' fn,coi 9n» 9n,s» Qn,2> 9n,co } выполнено

S>(/) = S (/)

Теорема 4.2. Для коллекции С £ {Cjv.M.n- ^N.M.n} выполнено

S>(C) = S (С)

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

Булеву функцию от п переменных можно представить в виде полинома Жегалкина47, причем существует взаимно-однозначное соответствие между булевыми функциями и полиномами Жегалкина:

/(xa,...*n)= © bfix"1 ...х"п, ЪаеЕ

5б£"

Сложность полинома Жегалкина §®(/) функции / определяется как число ненулевых коэффициентов Ьа. Сложности реализации булевых функций полиномами Жегалкина и конечньми автоматами не связаны друг с другом. Так, для функции /0, равной единице лишь на наборе 0" выполнено §®(/0) = 2" и §(/о) = " + 1- В свою очередь, сложность полиномов Жегалкина для булевых функций, представляемых сложными автоматами может кардинально отличаться.

Теорема 4.3. При р -> оо существуют функции и /„' для которых

,п+1 _ _

S(/„') = Sifn')~— 2®(/„')~пи §®Ш)~2". §>(/) = §(/)

Автоматная сложность классов Поста коррелирует с некоторыми другими мерами сложности. Например, классы Поста распадаются относительно логарифма мощности класса на те же 3 пояса. Для классов К первого пояса

43 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. 178-182

44 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

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

46 Körner 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

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

19

выполнено log|3C| = 0(2П)48'49,50,51. Для классов К второго пояса выполнено log \JC\ ~ О (т=)52,53,54'55- Для классов ОС третьего пояса log \К\ = 0(п).

Функция Шеннона для сложности схем из функциональных элементов для классов первого пояса имеет порядок О Для классов второго пояса — О fe)«*», для классов третьего пояса - 0(п).

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

В последнем параграфе приведены формулировки основных результатов в терминах QROBDD и ROBDD.

Заключение

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

2. Для классов Аи Л2, А3, Л4, D2, F22, Fj,Fi, F72, F2M, Ff, F6M, F? получены асимптотические оценки функции Шеннона и построены автоматы,

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

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

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

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

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

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

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

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

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

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

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

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

3. В ходе исследования автоматной сложности классов Поста ц >

3, для нетривиальных подмножеств этих классов получены нижние

асимптотические оценки функции Шеннона и построены автоматы, представляющие сложные функции.

4. Получены точные значения и асимптотика функции Шеннона для классов конечных языков £П(Л) и Построены автоматы, представляющие самые сложные коллекции языков. Такие автоматы моделируют процесс выбора одного из М возможных решений при N альтернативах на каждом шаге. Найден простой способ вычисления параметра р (высоты обратного дерева), входящего в состав формул сложности построенных автоматов. При этом не требуется сравнение величин вида 2П_Ч и 22* или обращение функций вида п(х) = 2х + х.

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

Благодарности. Автор выражает глубокую благодарность академику, профессору В.Б. Кудрявцеву и д.ф.-м.н., профессору Д.Н. Бабину за постановку задач, постоянную поддержку и внимание к работе.

Работы автора по теме диссертации

Основное содержание диссертации опубликовано в следующих работах автора:

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

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

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

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

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

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

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

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

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

Подписано в печать 20 ноября 2013 г. Объем 1,0 усл. п. л. Тираж 100 экз. Отпечатано в типографии «Реглет». Заказ № 268 119526 г. Москва, пр-т Вернадского, д. 39 www. reglet. Ru, тел. +7 495 363 78 90

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. ЛОМОНОСОВА

Механико-математический факультет

На правах рукописи

04201451667

Кибкало Мария Александровна

Автоматная сложность булевых функций из классов Поста

Специальность 05.13.17 — теоретические основы информатики

ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук

Научный руководитель доктор физико-математических наук, профессор Д.Н. Бабин

Москва-2013

Оглавление

Введение 3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение 107

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

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

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

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

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

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

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

Введение

§ 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-значный куб Ап = А х ... х А. Через Еп будем обозначать «-мерный двоичный куб. Ч�