В данном докладе рассматривается проблема K-конечнопорожденности для каждого предполного класса линейных автоматов, функционирующих над полем Галуа, состоящим из двух элементов, и в случае конечнопорожденности предъявляется базис. Также были выявлены некоторые свойства множеств линейных автоматов. В частности, это свойство сохранения последовательности в K-замыкании множества линейных автоматов, характеризующихся сохранением этой последовательности, и свойство сохранения в начальный момент времени булевых функций одной существенной переменной в K-замыкании множества линейных автоматов, где каждый автомат этого множества также обладает данным свойством.

линейные автоматы, выразимость, предполные классы

Бирюкова Вероника Андреевна,  Московский государственный университет