Часть 3. Математические модели

О свойстве аддитивного сдвига для линейной реализуемости автоматов

С. Б. Родин

Московский государственный университет имени М. В. Ломоносова, механико-математический факультет

Аннотация: Одним из необходимых условий для линейной реализуемости автомата является выполнения условия «аддитивного сдвига» на порождающих внутренней полугруппы автомата. «Аддитивный сдвиг» задается отображением на множестве состояний автомата. В данной работе изучаются такие отображения. Приведены свойства, которыми должно обладать отображение, чтобы задавать «аддитивный сдвиг». Так же показано, что такие отображения линейно реализуемы посредством неизбыточных кодирований и приведен явный вид получаемого оператора.

Ключевые слова: теория автоматов, переходные системы, подстановка, кодирование, сложность, булев оператор