The effect of partiality and adaptivity on the complexity of FSM state identification problems

Задача идентификации состояний в конечном автомате была и остается актуальной, поскольку используется во многих приложениях, в частности, при моделировании и тестировании дискретных управляющих систем. Для идентификации текущего состояния системы строятся так называемые установочные и синхронизирующие эксперименты с конечными автоматами, в то время как для идентификации начального состояния системы используются диагностические или различающие эксперименты. Установочные, синхронизирующие, диагностические или различающие эксперименты известны как «умозрительные» эксперименты с конечными автоматами, и методы синтеза входных последовательностей для таких экспериментов (если существуют) в настоящее время определены для недетерминированных и детерминированных, полностью и частично определенных автоматов, описывающих эталонное поведение системы. Известно, что проблема проверки существования и построения установочных, синхронизирующих, диагностических или различающих экспериментов существенно усложняется, если эталонное поведение системы описывается недетерминированным и частичным автоматом, что достаточно часто случается при описании сложных современных систем. Известно также, что в некоторых случаях сложность можно понизить, переключившись на адаптивный (условный) эксперимент с системой. В настоящей работе мы исследуем влияние частичности автомата и адаптивности эксперимента на сложность проверки существования и построения установочных, синхронизирующих, диагностических и различающих экспериментов для детерминированных и недетерминированных автоматов и иллюстрируем соответствующую сложность с использованием подходящих рисунков.