Аннотация доклада.

Работа посвящена важной как с прикладной, так и с теоретической точек зрения задаче кодирования (размещения) состояний автоматов, а именно, выбора способа кодирования, производящего к «лучшей» реализации автомата. В частности, изучаются линейно реализуемые автоматы, т.е. автоматы, обладающих тем свойством, что существует способ кодирования, при котором порождаемый им оператор является линейным. Приведен критерий линейной реализуемости автомата. Изучаются также такие автоматы, что все операторы, задаваемые всевозможными способами кодирования, являются различными. Приведен критерий того, что автомат обладает этим свойством. В заключении изучается как связаны класс автоматов, являющихся линейно реализуемыми, с классом автоматом, обладающим свойством, что все операторы, задаваемые всевозможными способами кодирования, являются различными. Показывается, что указанные классы автоматов имеют непустое пересечение, и ни один из классов не лежит в другом.