Об одном классе автоматов с полиномиальной оценкой числа состояний в наблюдаемой форме

Abstract

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

This work is devoted to the description of some property of a finite state machine (FSM), which allows one to speak about polynomial number of states in observable form of a FSM. The observable form is an essential part of the vast variety of methods for testing and optimization of systems, based on FSM model.