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

Введение

Глава I. Основные определения и краткий обзор результатов

§1. Основные определения и обозначения.

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

Глава II. Операторы в булевых функциях и их свойства

§3. Свойства операторов и операторных пучков.

§4. Два критерия существования базисных пучков.

§5. Специальные классы базисных пучков.

Глава III. Разложения булевых функций по операторным пучкам и невырожденным системам функций

§6. Разложения булевых функций по собственным образам операторного пучка.

§7. Операторные разложения по образам нечетных функций.

§8. Бинарные термы в разложениях.

§9. Разложения по невырожденным системам функций

Глава IV. Операторные канонические формы

§10. Общий вид операторных полиномиальных форм.

§11. Классы операторных форм.

§12. Иерархия классов операторных форм.

§13. Канонические формы с операторами других типов

Глава V. Сложность представлений и методы нахождения операторных полиномиальных форм

§14. Сложность операторных форм.

§15. Методы нахождения полиномиальных представлений

§16. Компьютерные реализации алгоритмов.

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

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

В теории булевых функций исследования, связанные с представлениями функций различными формами, интенсивно развиваются. Имеется большое количество работ по этому направлению, в частности [6, 20, 27, 28, 29, 47, 48, 52, 101, 109].

Первые результаты по представлениям булевых функций в виде полиномов были опубликованы в 1928 году в работах И.И.Жегалкина [17, 18]. Эти исследования были связаны с решением проблемы арифметизации логических рассуждений и не получили распространения в кругах, далеких от логики. И только с развитием теории кодирования в 50-е годы были продолжены исследования по полиномиальным представлениям булевых функций. В работах Д.Маллера [74] и И.Рида [83] полиномы Жегалкина были переоткрыты и получено их обобщение для введения нового класса линейных кодов, получивших название "коды Рида-Маллера", а введенные полиномиальные формы стали называться "формами Рида-Маллера".

Использование кодов Рида-Маллера для передачи изображений Марса американскими межпланетными станциями "Маринер" стимулировало широкие исследования этих кодов [26]. Однако все исследования проводились в направлении метрических свойств кодов, как подпространств. В обзоре [21] приведены более ста работ по этому направлению.

В это время ведутся исследования по различным направлениям теории булевых функций [45, 47, 50]. Появление интереса непосредственно к полиномиальным представлениям булевых функций, как объектам исследования, связано с практическими приложениями. Развитие электроники во второй половине двадцатого века в направлении увеличения быстродействия, уменьшения энергоемкости и стоимости привело к тому, что большая интеграция имеет теперь определяющее значение. Лучшей считается схема, имеющая меньшую площадь кристалла. Этот критерий плюс технологические требования регулярности структуры привели к требованию отображать на кристалл функцию или систему функций в виде дизъюнктивной, конъюнктивной или полиномиальной нормальной формы — матричной схемы. Такие схемы получили название программируемых логических матриц (ПЛМ) [7, 8, 11, 12, 69, 82, 84, 106].

Попытки напрямую перенести методы работы с ДНФ на ПНФ не принесли ощутимых результатов [44, 89]. Это стимулировало исследования по полиномиальным каноническим формам, так как имеется большое количество классов таких канонических представлений. По этому направлению имеется целый ряд публикаций и монографий [2, 4, 22, 39, 40, 41, 42, 49, 58, 66, 77, 78, 79, 80, 82, 91, 96, 98, 101, 104].

Внутренний стимул исследования этого направления — известные результаты О.Б.Лупанова по асимптотическим оценкам и разложениям булевых функций [23, 24, 25].

Методам минимизации полиномиальных представлений булевых функций и оценкам их сложности посвящены работы [9, 10, 13, 38, 44, 51, 53, 54, 55, 57, 59, 60, 62, 63, 64, 65, 68, 70, 73, 88, 90, 92, 93, 94, 99, 100, 102, 103, 105, 107, 108, 110].

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

Данная диссертация посвящена исследованиям по указанной проблематике.

Диссертация состоит из пяти глав, которые разбиты на 16 параграфов. Параграфы разбиваются на пункты.

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

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

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

Четвертая глава посвящена операторным полиномиальным каноническим формам булевых функций.

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

По результатам, изложенным в диссертации, имеется 28 публикаций [111 - 138]. Результаты докладывались на международных конференциях по алгебре, дискретной математике, математическом и прикладной логике, теоретической и технической кибернетике, в том числе было сделано несколько пленарных докладов (конференция по прикладной логике, Новосибирск, 1992; конференция по математической логике, Казань, 1992; 4-й семинар по дискретной математике и ее приложениям, Москва, 1993; школа-семинар "Дискретные модели в теории управляющих систем", Москва, 1993; X конференция по проблемам теоретической кибернетики, Саратов, 1993; III конференция по алгебре, Красноярск, 1993; школа-семинар "Сложность и синтез управляющих систем", Минск, 1993; школа-семинар "Сложность и синтез управляющих систем", Н.Новгород, 1994; конференция по математической логике, Новосибирск, 1994; конференция по прикладной логике, Иркутск, 1995; школа-семинар "Сложность и синтез управляющих систем", Минск, 1995; конференция "Автоматизация проектирования дискретных систем", Минск, 1995; конференция по проблемам теоретической кибернетики, Ульяновск, 1996; конференция "Мальцевские чтения", Новосибирск, 1997; Международная Сибирская конференция по исследованию операций, Новосибирск, 1998; конференция "Мальцевские чтения", Новосибирск, 1998; конференция "Математика и ее приложения", посвященная памяти профессора А.И.Кокорина и 275-летию РАН, Иркутск, 1999; Международная конференция "Логика и приложения", Новосибирск, 2000; Международная конференция по дискретному анализу и исследованию операций, Новосибирск, 2000; Международная конференция "Математика, информатика и управление", Иркутск, 2000; Международная конференция по проблемам в булевых функциях, Фрайберг (Германия), 2000; Международная конференция " Мальцев ские чтения", Новосибирск, 2000; XI Межгосударственная школа-семинар " Сложность и синтез управляющих систем", Нижний Новгород, 2000; 7-й Международный семинар "Дискретная математика и ее приложения", Москва, 2001).

Были сделаны доклады в ведущих научных центрах: Московский государственный университет (факультет вычислительной математики и кибернетики), Институт математики СО РАН (г. Новосибирск), Институт кибернетики им. В.М.Глушкова (г. Киев), Институт технической кибернетики (г. Минск), Институт динамики систем и теории управления СО РАН (г. Иркутск), Институт прикладной матаматики и кибернетики (г. Нижний Новгород) Институт информатики (г. Фрайберг, Германия), Иркутский государственный университет.

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

Заключение

На защиту выносятся следующие результаты:

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

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

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

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

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

1. Дискретная математика и математические вопросы кибернетики/ Под ред. Яблонского С.В. и Лупанова О.Б.-М: Наука, 1974.- Т1- 312 с.

2. Авгуль Л.Б. Супрун В.П. Обобщенные полиномиальные разложения симметрических булевых функций// Кибернетика.- 1991.- № 1.- С. 122-125.

3. Авсаркисян Г.С. Брайловский Г.С. Представление логических функций в виде полиномов Жегалкина// Автоматика и вычислительная техника.- 1975.- № 6.- С. 6-10.

4. Авсаркисян Г.С. Обобщенные полиномиальные формы булевых функций и синтез многовыходных логических схем// Автоматика и Телемеханика.- 1983.- № 11.- С. 111-119.

5. Авсаркисян Г.С. Представление булевых функций суммой по модулю 2 импликацией аргументов// Автоматика и вычислительная техника.- 1977.- №1.- С. 8—11.

6. Александров С Г. Разложения специального вида булевых функций// Международная конференция по дискретному анализу и исследованию операций. Материалы конференции.- Новосибирск, 2000.- С.70.

7. Артюхов В.JI., Копейкин Г.А., Шалыго А.А. Настраиваемые модули для управляющих логических устройств.-Ленинград: Энергоиздат, 1981.- 166 с.

8. Ачасова С.М. Алгоритмы синтеза автоматов на программируемых матрицах.- М.: Радио и связь, 1987.- 135 с.

9. Балюк А.С. Сложные в полиномиальных поляризованных формах симметричные булевы функции // XII Международная конференция по проблемам теоретической кибернетики: Тезисы докл.- Нижний Новгород, 1999.-С.17.

10. Балюк А.С. Сложные в полиномиальных поляризованных формах функции алгебры логики / / Международной конференции по математической логике: Тезисы докл.-Новосибирск, 1999.- С. 9- 10.

11. Баранова С.И., Скляров В.А. Цифровые устройства на программируемых СБИС с матричной структурой.- М.: Радио и связь, 1986.- 270 с.

12. Бибило П.Н. Синтез комбинационных ПЛМ структур для СБИС - Мн: Навука i тэхшка, 1992 - 232 с.

13. Бохманн Д., Постхоф X. Двоичные динамические системы.- М: Энергоатомиздат,

14. Гаврилов Г.П. Функциональные системы дискретной математики М: Изд-во Московского ун-та, 1985.- 40 с.

15. Глушков В.И. Введение в кибернетику.- Киев: Изд-во АН УССР, 1964.- 324 с.

16. Глушков P.M., Капитонова Ю.В., Мищенко А.Т. Логическое проектирование дискретных устройств.- Киев: На-укова думка, 1987.- 264 с.

17. Жегалкин И.И. Арифметизация символической логики // Мат. сборник.- 1928.- Т.35 С.311-373.

18. Жегалкин И. И. Арифметизация символической логики // Мат. сборник.- 1929.- Т.36 С.305-338.

19. Закревский А.Д. Минимизация систем булевых функций в полиномах Жегалкина// Докл. Белорусской АН.- 1995, т.39, № 6.- С.11-14.

20. Зубков О.В. Представление функций алгебры логики суммами специального вида // Межд. конф. "Логика и приложения", 4-6 мая 2000 г., Новосибирск., С. 52.

21. Кузнецов Ю.В., Шкарин С.А. Коды Рида-Маллера (обзор публикаций)// Математические вопросы кибернетики.-1996.- №1- С. 5-50.

22. Корсуков А.В. Разложение булевых функций с оператором векторная производная// В сб."Алгебра, логика и приложения". Иркутск, 1994. - С. 116-124.

23. Лупанов О.Б. Об одном подходе к синтезу управляющих систем — принципе локального кодирования// Проблемы кибернетики. Вып. 14 М.: Наука, 1965.- С. 31-110.

24. Лупанов О.Б. О сложности реализаций функций алгебры логики формулами// Проблемы кибернетики. Вып. 3. г из, 1963.- С. 61-80.

25. Лупанов О.Б. Асимптотические оценки сложности управляющих систем М.: Из-во МГУ, 1984 - 137 с.

26. Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов, исправляющих ошибки М.: Связь, 1979.- 477 с.

27. Марченков С.С. О равномерном id-разложении булевых функций// Дискретная математика.- 1990.- Т. 2, № 3.-С. 29-41.

28. Марченков С.С. Замкнутые классы булевых функций. -М.: Физматлит, 2000. 128 с.

29. Марченков С.С., Угольников А.Б. Замкнутые классы булевых функций.- М.: Ин-т прикл математики АН, 1990 — 147 с.

30. Мачикенас Э.К., Супрун В.П. О полиномиальном разложении булевых функций // Изд-во Белорусской АН, физмат. лит-ра, Минск.- 1988.- 31 с.

31. Нигматуллин Р.Г. Сложность булевых функций.- М.: Наука, 1991.- 240 с.

32. Пантелеев В.И., Перязев Н.А. Об операторах булевых функций// Материалы XI Межгосударственной школы-семинара "Синтез и сложность управляющих систем", Нижний Новгород, 2000. Из-во МГУ, Часть II. - С. 141146.

33. Перязев Н.А. Сложность булевых функций в классе полиномиальных поляризованных форм// Алгебра и логика.-1995.- Т. 34, № 3.- С. 323-326.

34. Перязев Н.А. Основы теории булевых функций. М.: Физматлит, 1999. - 112 с.

35. Поваров Г.Н. Математико-логическое исследование синтеза контактных схем с одним входом и к выходами// Логические исследования. Изд-во АН СССР.- 1959.- С.379-405.

36. Сапоженко А.А., Чухров И.П. Минимизация булевых функций в классе дизъюнктивных нормальных форм// ВИНИТИ. Итоги науки и техники. Теоретическая кибернетика.- 1987.- Вып. 25.- С. 68-116.

37. Сапоженко А.А., Караханян Л.М. Об отрицательных эффектах, связанных с удалением несущественных переменных// Автоматика и телемеханика. 1981. - №3. - С. 28-35.

38. Степин М.В., Кириченко К.Д. Некоторые стратегии при минимизации булевых функций// Материалы Международной научной студенческой конференции. Новосибирск. 1994. - С.38.

39. Супрун В.П. Преобразования булевых функций на основе симметрической разности// Изв. АН СССР. Техническая кибернетика. 1983. - №5. - С. 199-202.

40. Супрун В.П. Табличный метод полиномиального разложения булевых функций// Кибернетика.- 1987.- № 1.- С. 116-117.

41. Супрун В.П. Декомпозиция булевых функций на основе полиномиального разложения// Изв. АН СССР. Техническая кибернетика. 1989. - №3. - С. 187-191.

42. Супрун В.П. Об одном методе полиномиального разложения булевых функций// Кибернетика.- 1989.- № 5.-С. 122-124.

43. Супрун В.П. Сложность булевых функций в классе канонических поляризованных полиномов// Дискретная математика.- 1993.- Т. 5, Вып.2.- С.111-115.

44. Тошич Ж. Полиномиальные представления булевых функций и их минимизация// Известия АН СССР. Техн. кибернетика.- 1967.- № 3.- С. 141-143.

45. Шеннон К.Э. Работы по теории информации и кибернетике.- М: ИЛ., 1963.- 829с.

46. Яблонский С.В. Введение в дискретную математику.- М: Наука, 1986.- 384 с.

47. Яблонский С.В. О суперпозициях функций алгебры логики// Мат. сборник.- 1952.- Т. 30, № 2.- С. 329-345.

48. Яблонский С.В., Гаврилов Г.П., Кудрявцев В.Б. Функции алгебры логики и классы Поста.- М: Наука, 1966.- 120 с.

49. Akers S.B. A rectangular logic array. // Trans. IEEE.- 1972, vol. C-21.- P.848-857.

50. Akers S.J. On theory of Boolean functions // JSoc Industr and ApplMath.- 1959.- V.7, No 4.- P. 487-498.

51. Besslich Ph.W. and Riege M.W. An Efficient Program for Logic Synthesis of Mod-2 Sum Expressions // Proc. EU-ROASIC, Paris, France, 1991.- P.136-141.

52. Bochmann D. Boolean Differential Calculus — an Overview // in: Abel D., Lemmer K. Theory of discrete Systems.-Oldenbourg Verlag, 1998.- P. 161-201

53. Brand D. and Sasao T. Minimization of AND-EXOR expressions using rewrite rules // IEEE Transactions on Computers, 1993.- No 42(5).- P.568-576.

54. Bryant R.E. Graph-based algorithms for boolean function manipulation // IEEE Trans. Сотр.- 1986, vol. C-35, No. 8. P.667-691.

55. Brayton R.K. Factoring logic functions// IBM JRes and Dev.- 1987.- V.31, No 2.- P. 187-198.

56. Butler J.T., Herscovici D.S., Sasao Т., Barton III R.J. Average and worst case number of nodes in decision diagrams of symmetric multiple-valued funcsions// IEEE Trans, on Computers.- 1997.- V. 46, No 4.- P. 491-494.

57. Csansky L., Perkovsky M., Schaefer I. Canonical Restricted Mixed-Polatity Exclusive Sums of Products and Efficient Algorithm for Thier Minimization // Proc. IEEE International Symposumon Circuits and Systems. San Diego, 1992.- P.17-20.

58. Davio M. Taylor expansions of symmetric Boolean function// Philips Res. Repts.- 1973, No 28.- P. 466-474.

59. Debnath D., Sasao T. GRMIN: A Heuristic Simplification Algorithm for Generalized Reed- Muller Expressions // Proc. RM'95. P.257-264.

60. Drechsler R., Sarabi A., Theobald M., Becker В., and Perkowski M. Efficient representation and manipulation of switching functions based on Ordered Kronecker Functional Decision Diagrams // Proc. DAC'94.- P.415-419.

61. Drechsler R. Pseudo Kronecker Expressions for Symmetric Functions // Proc. VLSI Design, 1997.- P.511-513.

62. Drechsler R., Theobald M. and Becker B. Fast OFDD-based minimization of fixed polarity Reed-Muller expressions //

63. EE Trans. Comput., 1996.- Vol. C-45, No. 11- P.1294-1299.

64. Drechsler R. Evolutionary Algorithms for VLSI CAD. Kluwer Academic Publishers, 1998.- 350 p.

65. Drucker B.T., Files C.M., Perkowski M.A. and Chrzanows-ka-Jeske M. Polarized Pseudo-Kronecker Symmetry with an Application to the Synthesis of Lattice Decision Diagrams // Proc. ICCIMA'98, 1998.- P.123-132.

66. Even S., Kohavi J., Paz A. On minimal modulo-2 sums of products for switching functions // IEEE Trans. Electron. Comput.- 1967.- V.16, No 10.- P.671-674.

67. Fujita M.,(eds.) Representations of Discrete Function. Kluwer Academic Publishers, 1996.- 450 p.

68. Green D.H. Families of Reed-Muller Canonical Forms // Intern. J. of Electr 1991, No 2.- P.259-280.

69. Helliwell M. and Perkowski M.A. A fast algorithm to minimize mixed polarity generalized Reed-Muller forms // IEEE Computer Society Press, 1988.- P.427-432.

70. Ho P., and Perkowski M. A. Free Kronecker Decision Diagrams and their Application to ATMEL 6000 FPGA Mapping // Proc. Euro-DAC'94/Euro-VHDL'94.- P.8-13.

71. Kozlowsky T. Heuristic Minimization of ESOP's // Proc. Reed-Muller Colloquium. UK, 1995.- P. 4/1-4/5.

72. Lester N.L.K. and Saul J.M. Technology mapping of mixed polarity Reed-Muller representations //In Proceedings of the European Conference on Design Automation. IEEE Computer Society Press, 1993.

73. Mantsivoda J., Peryazev N. The Complexity of Symmetric Functions in the Polynomial Forms // 3rd International Workshop on Applications of the Reed-Muller Expansion in Circuit Design, Oxford/UK.- 1997.- FZI report 5/97.- P. 166-173.

74. Muller D.E. Application of Boollean algebra to switching circuit desing and error detectio// IEEE Trans. Electron. Comput.- 1954.- V.3, No 3.- P. 6-12.

75. Perkowski M., Johnson P. Canonical multi-valued input Reed-Muller Trees and Forms // Proc. 3rd NASA Symp. on VLSI Design. Oct. 1991, Moscow, Idaho.- P.ll.3.1-11.3.13.

76. Perkowski M.A. The Generalized Orthonormal Expansion of Functions with Multiple-Valued Inputs and Some of its Applications // Proc. ISM'L'92 P.442-450.

77. Perkowski M.A. A Fundamental Theorem for Exor Circuits // Proc. RM'93 P.52-60.

78. Perkowski M.A., Sarabi A., Beyl F. XOR Canonical Forms of Switching Functions // Proc. RM'93 P.27-32.

79. Perkowski M.A., Pierzchala E. and Drechsler R. Layout-Driven Synthesis for Submicron Technology: Mapping Expansions to Regular Lattices // Proc. ISIC-97, Singapur, 1997.- P. 29-37.

80. Reed I.S. A class of multiple-error-correcting codes and decoding scheme // IRE Trans. Inform. Theory.- 1954.- V. 4, N 9.- R 38-49.

81. Sarabi A., Song N., Chrzanowska-Jeske M. and Perkowski M.A. A Comprehensive Approach to Logic Synthesis and Physical Design for Two-Dimensional Logic Arrays // Proc. DAC'94.- San Diego, 1994.- P.321-326.

82. Sasao T. Multiple-Valued Decomposition of Generalized Boolean Functions and the Complexyty of Programmable Logic Arrays// IEEE Trans, on Comput.- 1981.- V. 30, No 9.- P. 633-645.

83. Sasao T. Input variable assignment and output phase optimization of PLA's // IEEE Trans. Comput., 1984.- Vol. C-33, No. 10.- P.879-894.

84. Sasao Т., Besslich P. On the complexity of mod-2 sum PLA's// IEEE Trans, on Comput.- 1990.- V. 39, No 2.-P. 262-266.

85. Sasao T. (editor) Logic Synthesis and Optimization. Kluwer Academic Publishers.- 1993 320 p.

86. Sasao Т. AND-EXOR expressions and their Optimization //in: Logic Synthesis and Optimization. Kluwer Academic Publishers.- 1993.- P. 289-300.

87. Sasao T. Represeintation of Logic Functions using EXOR Operators // Proc. IFIP WG 10.5 Workshop on Applic. of the Reed Muller Expansion in Circuit Design.- Tokyo, 1995.- P. 11-20.

88. Sasao T. (editor) Logic Synthesis and Optimization. Kluwer Academic Publishers.- 1993.- 320 p.

89. Sasao T. An Exact Minimization of AND-EXOR Expressions Using BDDs // Proc. Reed-Muller'93, P.91-98.

90. Sasao T. Complexity Measures for AND-EXOR Expressions // Proc. 3rd International Workshop on Applications of the Reed-Muller Expansion in Circuit Design.- Oxford/UK, 1997.- P. 145-156.

91. Sasao T. Switching Theory for Logic Synthesis.- Kluwer Academic Publishers.- 1999.- 355 p.

92. Schaefer I., Perkowski M.A. Multiple-Valued Input Generalized Reed-Muller Forms // IEE Proc., 1992.- Vol.139, No.6.-P.519-527.

93. Saul J.M., Eschermann B. and Juergen Froessl. Two-level logic circuits using EXOR sums of products // Combinational networks, 1993. In IEE Proceedings Part E, Computers and Digital Techniques U0(6).- P.348-356.

94. Saul J.M. An improved algorithm for the minimization of mixed polarity Reed-Muller representations // IEEE Computer Society Press, 1990.- P.372-375.

95. Saul J.M. An algorithm for the multi-level minimization of Reed-Muller representations // IEEE Computer Society Press, 1991.- P.634-637.

96. Saul J.M. Towards a mixed exdusive-/indusive-or factored form. In IFIP Workshop on Applications of the Reed-Muller Expansion in Circuit Design, 1993.- P. 1-5.

97. Saul J.M. An efficient data structure for the minimization of EXOR sums. IFIP WG10.5 Workshop on Applications of the Reed-Muller Expansion in Circuit Design, 1995.- P. 116-121.

98. Steibach В., Zhang Z. Synthesis for full testability of partitioned combinational circuits using Boolean differential calculus // Proc. of IEEE/ACM Int. Workshop in Logic Synthesis, USA, 1997.- P. 1-4.

99. Suprun V. Fixed polarity Reed-Muller Expansion of symmetric Boolean function // Proc. IFIP WG10.5 Workshop on Applications of the Reed-Muller Expansion in Circuit Design, 1995.- P. 246-249.

100. Thomson P. and Miller J.F. Symbolic method for simplifying AND-EXOR representations of Boolean functions using a binary decision technique and a genetic algorithm // IEE Proceedings-Computers and Digital Techniques.-1996.- Vol.143, No.2 P. 151-155.

101. Wood R.A. A Higt Density Programmable Logic Array Chip// IEEE Trans 1979.- V. 29, N 9.- P. 602-608.

102. Wu X., Chen X. and Hurst S.L. Mapping of Reed-Muller Coefficients and the Minimization of Exclusive-OR Switching Functions // IEE Proc.- 1982.- vol.129, No.l P.5-20.

103. Wu X., Perkowski M. Generalized Partially-Mixed-Polarity Reed-Muller Expansion and its Fast Computation // IEEE Trans, on Computers.- V.45, No.9.- P.1084-1088.

104. Yanushkevich S. Arithmetical Canonical Expansions of Boolean and MVL Functions as generalized Reed-Muller Forms // Proc. IFIP WG10.5 Workshop on Applications of the Reed-Muller Expansion in Circuit Design, 1995.- P. 300307.

105. Zeng X., Perkowski M.A., Dill K., Sarabi A. Approximate Minimization of Generalized Reed-Muller Forms // Proc. RM'95, P.221-230.

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

107. Винокуров С.Ф. Перязев Н.А. Полиномиальные разложения булевых функций по невырожденным функциям// Алгебра и логика.- 1991.- Т. 30, № 6.- С. 631-637.

108. Винокуров С.Ф. Полиномиальные операторные разложения и канонические формы булевых функций. Из-во Иркутского ун-та.- 1992.- 26 с.

109. Винокуров С.Ф. Перязев Н.А. Представление булевых функций полиномиальными формами// Кибернетика и системный анализ.- 1992.- № 2.- С. 210-213.

110. Винокуров С.Ф., Манцивода Ю.В., Перязев Н.А. Система автоматического синтеза частичных конечных автоматов на программируемых логических матрицах с памятью // Вычислительные системы, 146,- Новосибирск, 1992.- С. 142-143

111. Винокуров С.Ф. Перязев Н.А. Полиномиальная декомпозиция булевых функций // Математические заметки.-1993.- Т. 53, вып. 2. С. 25-29.

112. Винокуров С.Ф. Перязев Н.А. Разложение булевых функций на сумму произведений подфункций //Дискретная математика.- 1993 Т. 5, вып. 3. - С. 102-104.

113. Винокуров С.Ф. Перязев Н.А. Полиномиальные разложения булевых функций // Кибернетика и системный анализ,- 1993.- № 6.- С. 34-47.

114. Винокуров С.Ф. Манцивода Ю.В. Перязев Н.А. Минимизация булевых функций в классах нормальных форм методом разложения //В кн. Методы и системы технической диагностики. Из-во Саратовского университета.1993, вып. 18.- С. 39-40.

115. Винокуров С.Ф., Корсуков А.В. Полиномиальное разложение булевых функций по оператору векторной производной // III Международная конференция по алгебре. Сборник тезисов. Красноярск,- 1993.- С. 74.

116. Винокуров С.Ф., Перязев Н.А. Полиномиальные разложения булевых функций по неоднородным операторам / / Фундаментальные проблемы математики и механики. Математика М.: Изд-во Моск. ун-та, 1994 - С. 317-318.

117. Винокуров С.Ф., Гайдуков А.И. Класс стягиваемых булевых функций // XII Международная конференция по математической логике. Тезисы докладов.- Новосибирск,1994.- С. 38-39.

118. Винокуров С.Ф., Манцивода Ю.В., Перязев Н.А. Минимизация булевых функций в классах нормальных форм методом разложения // Фундаментальные проблемы математики и механики. Математика.- М.: Изд-во Моск. ун-та. 1994. С. 316-317.

119. Винокуров С.Ф., Гайдуков А.И., Корсуков А.В. Библиотека классов булевых функций // Сб. трудов Иркутского ГУ.- Иркутск, 1995.- Т.З.- С. 228-229.

120. Винокуров С.Ф., Манцивода Ю.В., Перязев Н.А. Система синтеза конечных автоматов // Тезисы докл. Международной конференции "Автоматизация проектирования дискретных систем",- Минск, 1995 С. 56.

121. Винокуров С.Ф., Гайдуков А.И., Корсуков А.В. Автоматизированная система для исследования булевых функций // Тезисы докл. Международной конференции "Автоматизация проектирования дискретных систем".-Минск, 1995.- С. 55.

122. Винокуров С.Ф., Гайдуков А.И. BOOLEARN — система для работы с булевыми функциями / / Международная конференция по прикладной логике: Тезисы докладов.-Иркутск, 1995.- С. 17-18.

123. Винокуров С.Ф. Некоторые оценки сложности булевых функций в классе полиномов // Синтез и сложностьуправляющих систем, VII Межгосударственная школа-семинар.- Минск, 1995.- С. 4-5.

124. Винокуров С.Ф. Перязев Н.А. Полиномиальная декомпозиция булевых функций по образам однородных операторов от невырожденных функций // Изв. ВУЗов. Математика.- 1996.- № 1 С. 17-21.

125. Винокуров С.Ф. Об одном классе полиномиальных форм булевых функций //XI Международная конференция по проблемам теоретической кибернетики. Тезисы докл-Ульяновск, 1996.- С. 220.

126. Винокуров С.Ф. Классификация булевых функций по оператору кратного минимума / / Международная Сибирская конференция по исследованию операций. Материалы конференции. Новосибирск, 1998.- С. 121.

127. Винокуров С.Ф. Представление операторных форм булевых функций последовательностями / / Материалы Международной конференции по математической логике. Новосибирск, 1999.- С. 12-14.

128. Винокуров С.Ф., Перязев Н.А. Полиномиальные разложения булевых функций по образам неоднородных операторов // Кибернетика и системный анализ.- 2000, № 4.- С. 40-55.

129. Балюк А.С., Винокуров С.Ф. Функция Шеннона для некоторых классов операторных полиномиальных форм //

130. Оптимизация, управление, интеллект.- 2000.- Вып 5.- С. 167-180.

131. Gaidukov A.I., Vinokurov S.F. Operator polynomial expansions of Boolean functions / / 4th International Workshop on Boolean Problems. Freiberg, Germany, 2000.- P.63-69.

132. Винокуров С.Ф. Смешанные операторы булевых функций и их свойства // Иркутский ун-тет. Серия: Дискретная математика и информатика. Вып. 12.- Иркутск, 2000.36 с.

133. Винокуров С.Ф. Разложения булевых функций по собственным операторным образам и термам над бинарными функциями // Оптимизация, управление, интеллект.- 2000.- Вып 4.- С. 167-180.

134. Винокуров С.Ф. Разложения булевых функций по операторам сплетения // Международная конференция "Логика и приложения". Тезисы докл. Новосибирск, 2000.- С. 31-32.

135. Винокуров С.Ф. Операторные полиномиальные представления булевых функций // Материалы XI Межгосударственной школы-семинара " Синтез и сложность управляющих систем".- М.: Изд-во Центра прикладных исследований МГУ, 2001.- С. 41-46.