Об обобщении теоремы Мура

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