О сложности реализации конечных языков регулярными выражениями и схемами

Одной из основных задач математической кибернетики является оптимальная реализация дискретных отображений различными средствами [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.