Разрешимость задачи полноты автоматного базиса в зависимости от его булевой частистатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 11 ноября 2019 г.
Аннотация:Рассматривается проблема полноты систем автоматных функций вида Φ ∪ ν с операциями суперпозиции и обратной связи, где Φ ⊆ P2, множество ν конечно. Решение этой
задачи приводит к разделению решетки замкнутых классов Поста на сильные (наличие
которых в исследуемой системе гарантирует разрешимость задачи полноты конечных ба-
зисов) и слабые (наличие которых в исследуемой системе этого не гарантирует). Оказа-
лось, что классификации базисов по свойству полноты и свойству А-полноты совпадают.
В данной статье описана эта классификация.