|
Интеллектуальные системы. Теория и приложения, 2019, том 23, выпуск 1, страницы 137–145
(Mi ista223)
|
|
|
|
Часть 3. Математические модели
О классификации базисов в $P_k$ по разрешимости полноты для автоматов
В. Б. Кудрявцев, Д. Н. Бабин
Аннотация:
Рассматривается проблема полноты систем автоматных функций с операциями суперпозиции и обратной связи вида $\Phi \cup \nu$, где $\Phi \subseteq P_k$, $\nu$ — конечно. При $k = 2$ решение этой задачи приводит к разделению решётки замкнутых классов Поста на сильные (наличие которых в исследуемой системе гарантирует разрешимость задачи полноты конечных базисов) и слабые (наличие которых в исследуемой системе этого не гарантирует). При $k = 2$ эта задача для систем автоматных функций произвольного вида была решена (Бабин Д.Н. 1998). В статье рассмотрены следствия и возможные обобщения этой задачи, а также некоторые результаты для
$P_k$, $k > 2$.
Ключевые слова:
булева функция, конечный автомат, алгоритмическая разрешимосить.
Образец цитирования:
В. Б. Кудрявцев, Д. Н. Бабин, “О классификации базисов в $P_k$ по разрешимости полноты для автоматов”, Интеллектуальные системы. Теория и приложения, 23:1 (2019), 137–145
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/ista223 https://www.mathnet.ru/rus/ista/v23/i1/p137
|
Статистика просмотров: |
Страница аннотации: | 128 | PDF полного текста: | 41 | Список литературы: | 18 |
|