Периодически внешне наследственные перестановочные автоматы

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