Аннотация:Данная работа посвящена изучению "линейно реализуемых" переходных систем, т.е. переходных систем, обладающих тем свойством, что существует кодирование, при котором порождаемый кодированием, булевкий оператор является линейным. В работе приведено необходимое условие линейной реализуемости переходной системы. Также приведены нижняя и верхняя оценка числа линейно реализуемых переходных систем.
Ключевые слова: теория автоматов, переходные системы, кодирование, сложность
The main purpose of the article is the investigation of "`linear realized"' semiautomata, i.e. semiautomata, which has the state encoding such as the boolean operator inspired by this state encoding is linear. The necessary criterion of linear realizing property is formulated in the article. Also the lower and upper bound estimation of linear realized semiautomata number are formulated.
Keywords: automata theory, semiautomata, transition systems, assignment, state encoding, complexity