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

Краткое описание

Орлов, Валентин Александрович.
Об особенностях асимптотического поведения сложности реализации к-значных и автоматных функций схемами в произвольном конечном базисе : диссертация ... доктора физико-математических наук : 01.01.09. - Москва, 1999. - 126 с. : ил.
Оглавление диссертациидоктор физико-математических наук Орлов, Валентин Александрович
ВВЕДЕНИЕ.
ГЛАВА 1. О СЛОЖНОСТИ РЕАЛИЗАЦИИ К-ЗНАЧНЫХ ФУНКЦИЙ СХЕМАМИ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ В ПРОИЗВОЛЬНОМ ПОЛНОМ КОНЕЧНОМ БАЗИСЕ
§ 1. Реализация булевых функций
§ 2. Реализация квазибулевых функций.
§ 3. Реализация к-значных функций
§ 4. Оптимальные базисы и сильно существенные системы к -значных функций
§ 5 Оценки числа сильно существенных функций.
§ 6 Об оптимальности почти всех &-значных базисов.
§ 7 О сравнении булевых и к -значных базисов
ГЛАВА 2. О СЛОЖНОСТИ РЕАЛИЗАЦИИ АВТОМАТНЫХ ФУНКЦИЙ СХЕМАМИ В ФУНКЦИОНАЛЬНО ПОЛНЫХ БАЗИСАХ
§ 8. Основные определения и формулировка результатов.
§ 9. Моделирование продукций Поста схемами в функционально полных базисах
§ 10. Описание автомата И
§11. Свойства схем в базисе Ве
§ 12. Доказательства основных результатов главы 2.
ГЛАВА 3. РЕАЛИЗАЦИЯ ФУНКЦИЙ СХЕМАМИ, В КОТОРЫХ ДОПУСТИМЫ СУЩЕСТВЕННЫЕ ЦИКЛЫ
§ 13. Реализация функций правильными схемами.
§ 14. Реализация функций С-схемами