О нижней оценке числа состояний детерминированных целесообразных автоматов

Изучается задача об оценке сложности детерминированных автоматов Мура, целесообразных в однородных марковских средах (ОМС). Мера сложности автомата определяется как число его внутренних состояний. Устанавливается нижняя оценка $N\geq 2k$, числа состояний автоматов, целесообразных в ОМС, улучшающая известную ранее оценку $N>k$ (здесь k – число управлений). Устанавливается нижняя оценка $N\geq k^{3/2}$ числа состояний автоматов, целесообразных в ОМС, при выборе любого их состояния в качестве начального.