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

• Орлова, Екатерина Валентиновна
• кандидат физико-математических наук
• 2000

Оглавление диссертации кандидат физико-математических наук Орлова, Екатерина Валентиновна

ВВЕДЕНИЕ.,.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Орлова, Екатерина Валентиновна, 2000 год

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.