|
Об алгоритмической разрешимости задачи об $A$-полноте для систем ограниченно-детерминированных функций, содержащих все одноместные $S$-о.-д. функции
В. А. Буевич, М. А. Подколзина
Аннотация:
Известно, что в общем случае задача об $A$-полноте конечных систем ограниченно-детерминированных функций алгоритмически неразрешима. Вместе с тем, критерий $A$-полноты может быть сформулирован в терминах $A$-предполных классов, а множество $A$-предполных классов описывается эффективно. В настоящей работе рассматриваются системы о.-д. функций, содержащие все о.-д. функции, зависящие от одной переменной и показано, что существует алгоритм для распознавания $A$-полноты таких систем.
Статья поступила: 22.12.2011
Образец цитирования:
В. А. Буевич, М. А. Подколзина, “Об алгоритмической разрешимости задачи об $A$-полноте для систем ограниченно-детерминированных функций, содержащих все одноместные $S$-о.-д. функции”, Дискрет. матем., 24:4 (2012), 56–69; Discrete Math. Appl., 22:5-6 (2012), 555–569
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm1210https://doi.org/10.4213/dm1210 https://www.mathnet.ru/rus/dm/v24/i4/p56
|
Статистика просмотров: |
Страница аннотации: | 339 | PDF полного текста: | 169 | Список литературы: | 46 | Первая страница: | 22 |
|