О конечных автоматах с максимальной степенью различимости состояний

Рассматривается оценка одного из параметров конечных автоматов - степень различимости состояний. В работе рассматриваются множества конечных автоматов с произвольными функциями выхода и переходов. Состояния конечного автомата называются r - эквивалентными, если соответствующие им автоматные функции одинаковы на словах длины r. Состояния называются r-различимыми, если они $(r-1)$ -эквивалентны и соответствующие им автоматные функции различаются на словах длины r. Максимальная степень различимости состояний автомата называется его степенью различимости. При отсутствии ограничений известна достижимая верхняя оценка степени различимости равная $s-1$, где $s$ - число состояний автомата. В каждом своем состоянии конечный автомат реализует функцию, аргументы которой (значения которой) суть элементы входного (выходного) алфавита. Число различных таких функций будем называть статической функциональностью автомата. Рассматриваются автоматы с заданной статической функциональностью. Получена достижимая верхняя оценка степени различимости, равная $s + 1 - F$, где $F$ - статическая функциональность автомата. Множество $\{s1, s2, . . . , s_F\}$, где $s_i$, $1 \le i \le$ $F$, -мощность i-го класса 1-эквивалентности будем называть спектром конечного автомата. Показана зависимость максимальной степени различимости состояний конечного автомата от его спектра.