Аннотация:
Данная работа посвящена изучению «линейно реализуемых» автоматов, то есть автоматов, обладающих тем свойством, что существует кодирование, при котором порождаемый кодированием, булевский оператор является линейным. В работе приведен критерий линейной реализуемости автомата. Также приведены нижняя и верхняя оценка числа линейно реализуемых автоматов.
Ключевые слова:теория автоматов, автомат, переходные системы, перестановка, подстановка, кодирование, сложность.
Полный текст:
PDF файл (157 kB)