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

• Автор: Орлова, Екатерина Валентиновна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2000
• Место защиты: Москва
• Количество страниц: 54 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ
ГЛАВА 1. РЕАЛИЗАЦИЯ КОНЕЧНЫХ ЯЗЫКОВ
РЕГУЛЯРНЫМИ ВЫРАЖЕНИЯМИ
§ 1. Основные определения
§ 2. Асимптотические оценки функционала Ьф(0,2, п)
§ 3. Сложность реализации дизъюнкций
§ 4. Функции, обращающиеся в единицу на г наборах
§5.0 реализации произвольных конечных языков
§ 6. Реализация языков с ограничениями на структуру регулярных выражений
ГЛАВА 2. РЕАЛИЗАЦИЯ КОНЕЧНЫХ ЯЗЫКОВ Я -СХЕМАМИ
§ 7. Асимптотически наилучший метод реализации произвольных
конечных языков
§ 8. Реализация одноэлементных языков
§ 9. Реализация полных и почти полных языков
§ 10. Реализация симметрических языков
ЛИТЕРАТУРА

ВВЕДЕНИЕ
Одной из основных задач математической кибернетики является оптимальная реализация дискретных отображений различными средствами [18].
Эта задача актуальна ввиду непрерывного возрастания потребности построения оптимальных устройств обработки цифровой информации.
Наиболее часто рассматривают следующие отображения: функции алгебры логики (булевы функции), функции к-значпой логики и ограниченно-детерминированные (автоматные) функции. Наиболее распространенными средствами реализации являются схемы различных видов: контактные и релейно-контактные схемы, схемы из функциональных элементов и схемы в автоматных базисах. В качестве критериев оптимальности схемы рассматривают сумму весов элементов (сложность), быстродействие и мощность.
Ввиду сложности задачи построения имеющей минимальную сложность схемы, реализующей произвольную функцию, часто ограничиваются изучением асимптотического поведения функционала, равного максимуму минимальных сложностей схем, реализующих функции из заданного класса.
В фундаментальных работах О. Б. Лупанова [5-12] получены асимптотики таких функционалов для класса всех булевых функций в случае контактных и релейно-контактных схем, формул и схем в произвольном конечном полном базисе, элементы которого не обладают памятью.
В работе исследуются вопросы сложности реализации конечных языков в произвольном конечном алфавите. В качестве средств реализации рассматриваются языки, каждый из которых состоит из

слова длины 1, и операции объединения, конкатенации и итерации языков. Рассматривается также реализация языков схемами, элементы которых реализуют эти операции. Такие схемы будем называть Я -схемами. Критерием оптимальности выбрана сложность (число операций). Большое внимание уделено вопросам реализации языков, являющихся множествами наборов, на которых булева функция принимает значение 1.
Из результатов А.Брауэра [20] и В.Штрассена [21] следуют оценки сложности реализации одноэлементных языков Л-схемами. При этом используется только операция конкатенации языков.
Отметим также работы Ю.В.Мерекина [13] , который привел пример набора, на котором достигается оценка В.Штрассена, и В.В.Кочергина [4], который получил асимптотически наилучшие и наилучшие по порядку оценки сложности реализации двоичных слов с заданным числом единиц схемами конкатенации.
Целью работы является исследование асимптотического поведения сложности реализации конечных языков в произвольном конечном алфавите регулярными выражениями и Я -схемами.
В работе использованы известные и разработанные автором методы асимптотической теории сложности управляющих систем, методы теории булевых и -значных функций и других разделов дискретной математики и математической кибернетики.
Все результаты диссертации являются новыми. Перечислим основные из них.
Предложен наилучший по порядку метод реализации произвольных конечных языков в произвольном конечном алфавите регулярными выражениями.
Разработан асимптотически наилучший метод реализации произ-