|
Записки научных семинаров ЛОМИ, 1975, том 49, страницы 131–158
(Mi znsl2796)
|
|
|
|
Финитно-аппроксимационный подход к изучению сложности рекурсивных предикатов
Р. И. Фрейдзон
Аннотация:
Рассмотрено расширение аксиоматики сложности М. Блюма, которое позволило исследовать сложность ограниченных аппроксимаций рекурсивных предикатов при весьма общих предположениях о типе вычислительного процесса. Доказан факт существования минимальных ограниченных аппроксимаций рекурсивных предикатов и возможность получения неулучшаемых оценок сложности минимальных ограниченных аппроксимаций. Получены окончательные оценки сложности ограниченных аппроксимаций при фиксированных понятиях вычислительного процесса (для конечных автоматов и для машин Тьюринга). Получена нижняя оценка сложности минимальных аппроксимаций для предиката “вхождение”. Библ. – 25 назв.
Образец цитирования:
Р. И. Фрейдзон, “Финитно-аппроксимационный подход к изучению сложности рекурсивных предикатов”, Теоретические применения методов математической логики. I, Зап. научн. сем. ЛОМИ, 49, Изд-во «Наука», Ленинград. отд., Л., 1975, 131–158
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl2796 https://www.mathnet.ru/rus/znsl/v49/p131
|
Статистика просмотров: |
Страница аннотации: | 124 | PDF полного текста: | 59 |
|