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