В данной работе вводится понятие локальной неисправности на функциональном уровне. Последовательности таких неисправностей образуют локально порожденный класс автоматов. В работе изучается структура локально порожденного класса автоматов и его место в традиционном классе неисправностей. Также рассматривается задача распознавания контрольного эксперимента относительно заданного класса автоматов. Показано, что задача распознавания в случае локально порожденного класса автоматов решается полиномиальным алгоритмом, а в случае класса всех автоматов с заданным числом состояний является полиномиально полной.

теория конечных автоматов, локальные неисправности автоматов, задача распознавания контрольного эксперимента

Математические вопросы и теория численных методов