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

Московский государственный университет имени М.В. Ломоносова

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

На правах рукописи УДК 519.6

РГБ ОД ОРЛОВА 2 2 МАЙ 2009

Екатерина Валентиновна

О СЛОЖНОСТИ РЕАЛИЗАЦИИ КОНЕЧНЫХ ЯЗЫКОВ РЕГУЛЯРНЫМИ ВЫРАЖЕНИЯМИ И

СХЕМАМИ

Специальность 01.01.09 — математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва-2000

Работа выполнена на кафедре дискретной математики механико-математического факультета Московского государственного университета имени М.В. Ломоносова

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

Официальные оппоненты:

Ведущая организация:

доктор физико-математических наук, профессор Л.А. Шоломов

кандидат физико-математических наук H.A. Карпова

Институт математики им. С.Л. Соболева Сибирского отделения РАН

Защита диссертации состоится " 16" 1СЮНЛ-' 2000 г. в 16 ч. 15 мин. на заседании диссертационного совета Д.053.05.05 при Московском государственном университете им М.В.Ломоносова по адресу:

119899, ГСП, Москва, Воробьевы горы, МГУ, мсханико-математи-чсский факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан "/б"» мая 2000 г. Ученый секретарь

диссертационного совета В.Н.Чубариков

Д.053.05.05 при МГУ д.ф.-м.н., профессор

3 о

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

В фундаментальных работах О. В. Лупанова 2 3 4 5 получены

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

2Лупанов О.В. О синтезе контактных схем // ДАН СССР.- 1958,- Т.119, N 1,- С.23-26.

'Лупанов О.Б. Об одном методе синтеза схем. // Изв. вузов, Радиофизика. -

1958.- Т.1, N.I.- С. 120-140.

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

5 Л упанов О.В. О сложности реализации функции алгебры логики релейно-

контактными схемами.// Проблемы кибернетики. Вып. 11.- М.:Наука, 1964.-

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

В работе исследуются вопросы сложности реализации конечных языков в произвольном конечном алфавите. В качестве средств реализации рассматриваются языки, каждый из которых состоит из слова длины 1, и операции объединения, конкатенации и итерации языков. Рассматривается также реализация языков схемами, элементы которых реализуют эти операции. Такие схемы будем называть Л-схемами. Критерием оптимальности выбрана сложность (число операций). Большое внимание уделено вопросам реализации языков, являющихся множествами наборов, на которых булева функция принимает значение 1.

Из результатов А.Брауэра 6 и В.Штрассена 7 следуют оценки сложности реализации Л-схемами языков, состоящих из одного слова. При этом используется только операция конкатенации языков. Отметим также работы Ю.В.Мерекина 8 , который привел пример набора, на котором достигается оценка В.Штрассена, и

B.В.Кочергина 9 , который получил асимптотически наилучшие

C. 25-48.

«Brauer A., On addition chains // Bull. Amer. Math. Soc., 1939, v.45, p. 736739.

'Strassen V., Berechnungen in partiellen Algebren endlichen Typs // J. of Computing, 1973, v. 11, p. 181-196.

'Мерекин Ю.В. Нижняя оценка сложности для схем конкатенации слов // Дискретный анализ и исследование операций. — 1996. Т. 3 , N 1. — С. 52-56.

'Кочергин В.В. О сложности сложности реализации двоичных слов с заданным числом единиц схемами конкатенации // Труды III Международной конференции "Дискретные модели в теории управляющих систем" (22-27 июня 1998 г.). — М.: Диалог-МГУ, 1998. — С. 58-62.

и наилучшие по порядку оценки сложности реализации двоичных слов с заданным числом единиц схемами конкатенации.

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

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

Научная новизна. Все результаты диссертации являются новыми. Перечислим основные из них.

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

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

Получены асимптотически наилучшие и наилучшие по порядку оценки сложности реализации регулярными выражениями и Я -схемами языков заданной мощности и симметрических языков.

Теоретическая и практическая ценность. Диссертация носит теоретический характер. Исследовано асимптотическое поведение сложности реализации произвольных конечных языков в произвольном конечном алфавите регулярными выражениями и Я -схемами. Получены также результаты о сложности реализации некоторых классов языков. Результаты работы и предложенные методы найдут применение в области оптимальной реализации языков с использованием операций объединения, конкатенации

и итерации.

Апробация работы и публикации. Результаты диссертации в 1996-1999 годах докладывались на XI международной конференции по теоретическим проблемам кибернетики (Ульяновск, 1996 г.), на VI международном семинаре по дискретной математике и ее приложениям (Москва, 1998г.) и на XII международной конференции по теоретическим проблемам кибернетики (Нижний Новгород, 1999 г.).

Все основные результаты диссертации опубликованы. По теме диссертации автором опубликованы 3 печатные работы. Работ, выполненных в соавторстве, нет.

Структура работы. Диссертация состоит из введения, двух глав и списка литературы. Глава 1 разбита на 6 параграфов, глава 2 - на 4 параграфа. Список литературы содержит 21 наименование. Общий объем работы составляет 54 страницы текста. Изложение иллюстрируют 2 рисунка.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

Словом в алфавите называется конечная последовательность букв этого алфавита. Языком в алфавите называется множество слов в этом алфавите.

Язык, состоящий из слов одинаковой длины, будем называть однородным. Однородный язык с равной п длиной слова будем называть п-однородном. Без ограничения общности под алфавитом будем понимать алфавит Ек = {0,1,..., к — 1}, к > 2.

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

Пусть Я1 и Яг — произвольные языки. Через Я1 и Я2 обозначают объединение языков Я1 и Яг, а через Я1 х Яг — множество всех слов, каждое из которых является конкатенацией слова из Ях и слова из Яг. Через *Я\ обозначается 1)^=1 Я}, где Я} = Я[ и

Я^ЯГ1 хЯъ п>2.

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

1°. Буква алфавита является языком регулярных выражений.

2°. Если Я1 и Яг — языки регулярных выражений, то Я1 и Яг, Я] х Я2 и *Я1 также являются языками регулярных выражений.

3°. Других языков регулярных выражений нет.

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

Всюду в дальнейшем под формулой будем понимать формулу над базисом {и, х}. Под сложностью формулы будем понимать число операций и и х. Через Ьф(Я) обозначим минимум сложностей формул, задающих язык Я, а через Ьф(М) — максимум Ь ф(Я) по всем языкам Я из множества М. Через Л4,„ обозначим множество языков в алфавите Е^ с максимальной длиной слова, равной п, а через Мо,к,п — множество п-однородных языков в алфавите Е^. Пусть Ь<р(к, п) = Ьф(Мк<п)

и Ьф(0, к. п) = Ьф(Мо,к.„)-

Двухполюсная последовательно-параллельная сеть, все дуги которой ориентированы естественным образом (от входа к выходу), называется 7г-сетью. Являющуюся параллельным (последовательным) соединением подсетей тг-сеть будем называть р-сетью [я-сетью). Эти подсети будем называть главными компонентами 7г-сети. Отметим, что (непустые) главные компоненты р-сети (а-сети) являются 5-сетями (р-сетями).

Будем называть (эт, к)-схемой 7Г-сеть, дугам которой приписаны буквы алфавита Ек- Формуле в алфавите Ек поставим в соответствие (-7Г, А;)-схему. При этом операции и (х) соответствует параллельное (последовательное) соединение подсхем. Формуле а, а 6 Ек, ставим в соответствие (тг, А;)-схему, состоящую из инцидентной ее входу и выходу дуги, которой приписан символ а.

Таким образом, формуле соответствует единственная (*7г, к)-схема.

Пусть формула Ф задает язык Я в алфавите Ек. Скажем, что (тт, А;)-схема, соответствующая формуле Ф, реализует язык Я.

Под сложностью (%, к)-схемы будем понимать число ее дуг. Через Ьп(Я) обозначим минимум сложностей (7Г, А:)-схем, реализующих язык Я в алфавите Ек, а через Ь Т(Л/) — максимум Ь Л(Я) по всем языкам Я из множества М. Пусть ЬТ(к, п) = Ьж(Мк,п) и

Ьъ(0, к,п) = Ь„(М0,к,п)-

Известно, что для любого конечного языка Я имеет место равенство

Ьж( Я) = £Ф(Я) + 1.

Через /V/ обозначается множество наборов, на которых булева функция / равна 1. Таким образом, булевой функции / от п

переменных соответствует являющийся »-однородным язык Nj в алфавите E¿. Ввиду этого не будем различать булеву функцию / и соответствующий ей (однородный) язык N¡. Следовательно, вопрос о реализации однородных языков в алфавите E¿ регулярными выражениями сводится к задаче реализации булевых функций (т. 2)-схемами. Это дает возможность использовать достаточно хорошо разработанную теорию оптимального синтеза булевых функций.

Пусть D„ — множество всех дизъюнкций arf1 V V ... V , пусть Fk,n,r — множество всех гг-однородных языков мощности г в алфавите Ек и пусть Dk,n = Fkln,k"-1-

В первой главе диссертации получены оценки функционалов Ьф(0. к, п), Ьф(к,п), L<t>(Dn), L<t,(Fk,n,r) и L^{Dk,n)-

Для простоты изложения приведены доказательства утверждений о сложности реализации однородных языков в алфавите E-¿.

Основными результатами § 2 являются установление соотношения Lп(0.2, п) ~ <т2" и получение оценок константы а.

Теорема 2.

Ьф(0.2, п) ~ а 2" , где а — константа из интервала (0,4164 ;1].

В § 3 рассматривается реализация дизъюнкций.

Всюду в дальнейшем через loga будем обозначать log2 а.

Теорема 3.

3

nlogn~ Ьф{Вп) ~ -nlogn.

Для сравнения отметим, что, используя полученную В.М. Храп-

ченко 10 нижнюю оценку, нетрудно показать, что сложность реализации регулярными выражениями линейной функции от п переменных по порядку равна п2 (как и в случае обычных 7Г-схем).

В § 4 рассматриваются функции, обращающиеся в единицу на заданном числе наборов.

Теорема 4. Для любого г < 2!ге/,21

Ьф(^2,я,г) ~ г(п - log г).

Теорема 5. При г = 2сп, се [1/2; 1), L<s>{F2,n,v) ^ r(n-log г).

Для любых пит, п.—1 < m < 2[п/2]+2)—5 построен

язык в алфавите Е-г, имеющий разную m сложность реализации регулярными выражениями. Описание этих языков конструктивно (не используется понятие "сложность реализации").

В § 5 рассматривается реализация произвольных конечных языков.

Теорема в.

£Ф(2,п) ~ <т\ 2",

где сг1 — константа из интервала (0,4164; 2].

'"Храпченко В.М. О сложности реализации симметрических функций формулами К Математические заметки. — 1972. — Т. 11, вып. 1. — С. 109-120.

Теорема 7. Для любого к > 3

Ьф(0, к. а) ~ гт2кп ,

где <72 — зависящая от к константа такая, что

4 + к

1

Теорема 8. Для любого к > 3

Ьф(к, а) ~ <Тзкп , где <7з —- зависящая от к константа такая, что

-\—- < <Т3 <

4 + 1ой к ~ ~

1 к

к^ к к — 1 '

Имеют место аналоги результатов, полученных в § 3 и 4, для случая произвольного к > 3.

Например, имеет место соотношение

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

Рассмотрим следующую классификацию тг-сетей. Состоящую из одной дуги 7г-сеть назовем (р. 0)-сетью или (в,0)-сетью. Назовем (р, г)-сетью ((в, г)-сеть»), г > 1, р-сеть (я-сеть), одна из главных компонент которой является (а, г — 1)-сетью ((р, г — 1)-сетью), а остальные главные компоненты — (а, ^)-сети ((р. У)-сети), у < ¿ — 1. Классификацию (тг, Ь)-схем проводим по аналогии. Например, (р, г, А:)-схемой будем называть (тг, А:)-схему, которой соответствует (р, ¿)-сеть.

Ьф(АЬ,П) ~ nlogn.

Через 1Лрл)(Я) Я)) будем обознать минимум сложностей

(р.2. А:)-схем ((в, У, А:)-схем), у < реализующих язык Я в алфавите Ек- Обозначения остальных функционалов аналогичны.

Нетрудно проверить, что произвольный конечный язык в алфавите Ек можно реализовать (р. г, к)-схемой при г > 2.

Для любого /г имеют место следующие легко проверяемые оценки

С,$Я{0,к,п) =

1=1 ЛГ — X

Теорема 9. Для любого к

Ь^(0.к,п) ~ пй"-1.

Для любого к имеет место следующее соотношение

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

Назовем (р, 4, к,^)-схемогI (р, 4, &)-схему, в которой максимальное число (р, г )-компонент, г > 1, ее главных компонент равно ]. Через ¿^'''^(Я) будем обознать минимум сложностей (р, 4, А:, ¿)-схем, I < реализующих язык Я в алфавите Е^.

Теорема 10. ГГри г = о(п)

£!рАг)(0,2,п) ~ 2".

Отметим, что можно построить (р. 4,2)-сеть, число дуг которой асимптотически равно 2П, такую, что приписыванием ее дугам

символов алфавита Е2 можно реализовать любой булев п-однородный язык. Из теоремы 10 следует, что эта сеть является асимптотически наилучшей в классе (р. 4, г)-сетей.

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

Л-схема (в алфавите Еь) имеет к входов, которым приписаны символы алфавита Ек- Элемент /? -схемы, реализующий операцию х (и, *), будем обозначать через Е-К (Ей, Е,). Элементы К -схемы соединяются по правилам построения схем из функциональных элементов. Отметим, что регулярному выражению соответствует Я-схема, в которой выход элемента соединяется со входом не более одного элемента (схема без ветвления выходов элементов).

Под сложностью Я-схемы будем понимать число ее элементов. Через Ь я (Я) обозначим минимум сложностей Я -схем, реализующих язык Я, а через Ьц(М) — максимум Ьц(Я) по всем языкам Я из множества М. Пусть Ьн(к,п) = Ья(Мк,п) и Ьв(0, к, п) = Ьц(М0,к,п)-

В § 7 получены асимптотики функционалов Ьй(0,к,п) и Ьц(к, п) для произвольного к > 2. Верхняя оценка получается модификацией метода О.Б.Лупанова асимптотически наилучшей реализации булевых функций схемами из функциональных элементов 11. Нижняя оценка получается из обычных мощностных соображений.

"Лупанов О.Б. О синтезе некоторых классов управляющих систем // Сб."Проблемы кибернетики", вып. 10, М., 1063, Физ- матгнз, С. 63 - 97.

Теорема 11. Для любого к > 2

к"

Lit (О, к. ")

п log к

Теорема 12. Для любого к >2

к к"

LR(k, п)

к — 1 п log к

В § 8 приведены результаты А. Брауэра и В. Штрассена, из которых следуют оценки сложности реализации одноэлементных языков.

Через Кк,п обозначим множество языков в алфавите Ек, каждый из которых состоит из слова длины п.

Язык назовем симметрическим, если наряду со словом W он содержит все слова, получаемые из слова W перестановкой букв.

Через К£ а обозначим множество симметрических языков из множества Кь,п-

Из результата А. Брауэра следует, что для любого к имеет место соотношение

Из результата В. Штрассена следует, что для любого к имеет место соотношение

п log к

LR(Kk,n)

log п

Таким образом, сложность реализации состоящих из одного слова языков в классе Д -схем зависит от структуры слова. Заметим, что сложность реализации таких языков регулярными выражениями одинакова.

В § 9 рассмотрена реализация полных и почти полных языков.

Язык, состоящий из всех слов в алфавите Ек, длина которых не превосходит п, будем обозначать через Щ.

Язык, состоящий из всех слов в алфавите Ек, длина которых равна п, будем обозначать через Е£-

Для любых кап имеет место соотношение

1ц(ЕП ~ log п.

Через Dj! п обозначим множество симметрических языков из множества

Теорема 13. Для любого к

Теорема 14. Для любого к

lOg 71

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

Отметим также что сложность реализации однородных языков, состоящих из одного слова и выпускающих одно слово, в классе Я-схем одинакова по порядку. Из теоремы 3 следует, что сложности реализации таких языков регулярными выражениями имеют разные порядки.

Из легко проверяемых представлений

и nl+J = (Щ х П{) U Ек

нетрудно получить следующие оценки

кп < £Ф(Щ) < к (2п - 1). \ognZ Ьц(Щ)$21оё п.

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

Через ПЩ „ обозначим множество симметрических языков из множества ПЩ1П.

Имеют место следующие оценки

В § 10 рассмотрена реализация симметрических языков. Для простоты изложения будем рассматривать однородные симметрические языки в алфавите Еъ-

Однородный симметрический язык называется элементарным, если он состоит из слов, получаемых из одного слова перестановкой букв. Через Эп>1-, 0 < г < п, обозначим элементарный язык (в алфавите Е-^), состоящий из имеющих г единиц слов длины п, а через ЭТ1 — множество всех таких языков. Нетрудно проверить, что любой ^-однородный симметрический язык является объединением языков из множества Эп.

Через Э"'"1'1 (Эп,т,°) обозначим систему всех языков Эп,,-

ЬН(ПЩ,П) ж 1о§гг и

(Эп,„_,-), 0 < г < т.

п,п—»

Лемма 15. Для любого т

Ьп(Э"'пЛ) ~ (т + 1)21ойп и Ья{Э""'-°) £ (т+1)21оёп.

Через М* обозначим множество п-однородных симметрических языков в алфавите Е-2-

Лемма 16.

Через БМ* обозначим систему всех га-однородных симметрических языков в алфавите Е2.

Теорема 15.

Ьа(ЗМ') ~ 2П+1.

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

Публикации по теме диссертации

1. Орлова Е.В. Реализация булевых функций регулярными выражениями // Тезисы докладов XI международной конференции по проблемам теоретической кибернетики, М., РГГУ, 1996, С. 155-156.

2. Орлова Е.В. О сложности регулярных выражений для функций из некоторых классов // Тезисы докладов XII международной конференции по проблемам теоретической кибернетики, М., Изд-во мех-мат ф-та МГУ, 1999, С. 181.

3. Орлова Е.В. О сложности реализации конечных языков формулами // Дискретная математика. — 2000. — Т. 12, вып. 1. — С. 145-157.

ВВЕДЕНИЕ.,.

ГЛАВА 1. РЕАЛИЗАЦИЯ КОНЕЧНЫХ ЯЗЫКОВ

РЕГУЛЯРНЫМИ ВЫРАЖЕНИЯМИ

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

§ 2. Асимптотические оценки функционала Ьф(0, 2, п).

§ 3. Сложность реализации дизъюнкций.

§ 4. Функции, обращающиеся в единицу на г наборах.

§ 5. О реализации произвольных конечных языков

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

ГЛАВА 2. РЕАЛИЗАЦИЯ КОНЕЧНЫХ ЯЗЫКОВ Д-СХЕМАМИ

§ 7. Асимптотически наилучший метод реализации произвольных конечных языков.

§ 8. Реализация одноэлементных языков.

§ 9. Реализация полных и почти полных языков.

§ 10. Реализация симметрических языков

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

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

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

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

В фундаментальных работах О. Б. Лупанова [5-12] получены асимптотики таких функционалов для класса всех булевых функций в случае контактных и релейно-контактных схем, формул и схем в произвольном конечном полном базисе, элементы которого не обладают памятью.

В работе исследуются вопросы сложности реализации конечных языков в произвольном конечном алфавите. В качестве средств реализации рассматриваются языки, каждый из которых состоит из слова длины 1, и операции объединения, конкатенации и итерации языков. Рассматривается также реализация языков схемами, элементы которых реализуют эти операции. Такие схемы будем называть Я -схемами. Критерием оптимальности выбрана сложность (число операций). Большое внимание уделено вопросам реализации языков, являющихся множествами наборов, на которых булева функция принимает значение 1.

Из результатов А.Брауэра [20] и В.Штрассена [21] следуют оценки сложности реализации одноэлементных языков Я -схемами. При этом используется только операция конкатенации языков.

Отметим также работы Ю.В.Мерекина [13] , который привел пример набора, на котором достигается оценка В.Штрассена, и В.В.Кочергина [4], который получил асимптотически наилучшие и наилучшие по порядку оценки сложности реализации двоичных слов с заданным числом единиц схемами конкатенации.

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

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

Все результаты диссертации являются новыми. Перечислим основные из них.

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

Разработан асимптотически наилучший метод реализации произ5 вольных конечных языков в произвольном конечном алфавите Я -схемами.

Получены асимптотически наилучшие и наилучшие по порядку оценки сложности реализации регулярными выражениями и Л-схемами языков заданной мощности и симметрических языков.

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

1. Глушков В.М. Синтез цифровых автоматов, М., Физматгиз, 1962.

2. Клини С.К. Представление событий в нервных сетях и конечных автоматах // Сб. "Автоматы" под редакцией К.Э.Шеннона и Дж.Маккарти, ИЛ, М., 1956.

3. Кнут Д. Искусство программирования для ЭВМ, т.2, М., Мир, 1977.

4. Кочергин В.В. О сложности сложности реализации двоичных слов с заданным числом единиц схемами конкатенации // Труды III Международной конференции "Дискретные модели в теории управляющих систем" (22-27 июня 1998 г.). — М.: Диалог-МГУ, 1998. — С. 58-62.

5. Лупанов О.Б. О синтезе контактных схем // Докл. АН СССР. — 1958.- Т.119, N 1.— С. 23-26.

6. Лупанов О.Б. Об одном методе синтеза схем // Изв. вузов, Радиофизика.- 1958.- T.l, N.1 С. 120-140.

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

8. Лупанов О.Б. О реализации функций алгебры логики формулами из конечных классов (формулами ограниченной глубины) в базисе V, -I // Проблемы кибернетики, вып. 6, М., Физматгиз, 1961.

9. Лупанов О.Б. Об одном классе схем из функциональных элементов (формулы с частичной памятью) // Проблемы кибернетики. Вып. 7 М.: Физматгиз, 1962 - С. 61-114.

10. Лупанов О.Б. О синтезе некоторых классов управляющих систем // Сб."Проблемы кибернетики", вып. 10, М., 1963, Физматгиз, С. 63 97.

11. Лупанов О.Б. О сложности реализации функции алгебры логики релейно-контактными схемами // Проблемы кибернетики. Вып. 11- М.:Наука, 1964.- С. 25-48.

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

13. Мерекин Ю.В. Нижняя оценка сложности для схем конкатенации слов // Дискретный анализ и исследование операций. — 1996. Т. 3 , N 1. — С. 52-56.

14. Орлова Е.В. Реализация булевых функций регулярными выражениями // Тезисы докладов XI международной конференции по проблемам теоретической кибернетики, М., РГГУ, 1996.

15. Орлова Е.В. О сложности регулярных выражений для функций из некоторых классов // Тезисы докладов XII международной конференции по проблемам теоретической кибернетики, М., Изд-во мех-мат ф-та МГУ, 1999.

16. Орлова Е.В. О сложности реализации конечных языков формулами // Дискретная математика. — 2000. — Т. 12, вып. 1. — С. 145-157.54

17. Храпченко В.М. О сложности реализации симметрических функций формулами // Математические заметки. — 1972. — Т. 11, вып. 1. — С. 109-120.

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

19. Яблонский С.В. Введение в дискретную математику, М., Наука, 1979.

20. Brauer А., On addition chains // Bull. Amer. Math. Soc., 1939, y.45, p. 736-739.

21. Strassen V., Berechnungen in partiellen Algebren endlichen Typs // J. of Computing, 1973, v. 11, p. 181-196.