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

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