Solvability of the Problem of Completeness of Automaton Basis Depending on its Boolean Partстатья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 29 мая 2019 г.
Аннотация:We consider the problem of completeness of systems of automaton functions with operations of superposition and feedback of the form Φ ∪ ν,where Φ ⊆ P2,and ν is finite. The solution of thisproblem leads to separation of the lattice of closed Post classes into strong ones (whose presence inthe system under consideration guarantees the solvability of the completeness problem of finite bases)and weak ones (whose presence in the system under consideration does not guarantee this solvability).It turns out that the classifications of bases by completeness and A-completeness properties coincide.The paper describes this classification.