|
Дискретная математика, 1995, том 7, выпуск 1, страницы 52–65
(Mi dm558)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Неразрешимость проблемы полноты и A-полноты некоторых систем автоматных функций
Д. Н. Бабин
Аннотация:
Рассматриваются системы автоматных функций $\mathfrak M=\Phi\cup\mathfrak N$, где $\Phi$ — некоторый класс Поста, а $\mathfrak N$ — конечная система автоматных функций. Показано, что если $\Phi$ — класс Поста типа $F^\infty$, $S$, $P$ или $O$, то проблема полноты и A-полноты для системы $\mathfrak M$ алгоритмически неразрешима.
Статья поступила: 25.05.1993
Образец цитирования:
Д. Н. Бабин, “Неразрешимость проблемы полноты и A-полноты некоторых систем автоматных функций”, Дискрет. матем., 7:1 (1995), 52–65; Discrete Math. Appl., 5:1 (1995), 31–42
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm558 https://www.mathnet.ru/rus/dm/v7/i1/p52
|
Статистика просмотров: |
Страница аннотации: | 276 | PDF полного текста: | 87 | Первая страница: | 2 |
|