000			05225nab a2200313 c 4500
001			vtls000646097
003			RU-ToGU
005			20230123130243.0
007			cr |
008			181220|2018 ru s c rus d
024	7		_a10.15514/ISPRAS-2018-30(4)-9 _2doi
035			_ato000646097
040			_aRU-ToGU _brus _cRU-ToGU
100	1		_aТвардовский, Александр Сергеевич _997109
245	1	0	_aК синтезу адаптивных различающих последовательностей для конечных автоматов _cА. С. Твардовский, Н. В. Евтушенко
246	1	1	_aDeriving adaptive distinguishing sequences for finite state machines
504			_aБиблиогр.: 11 назв.
520	3		_aКонечные автоматы широко используются при построении проверяющих тестов для управляющих систем с гарантированной полнотой обнаружения неисправностей. В ряде случаев такие тесты достигают экспоненциальной длины относительно размеров автомата-спецификации, что мотивирует исследования по оптимизации проверяющих тестов. Существование последовательностей, различающих каждую пару состояний в автомате-спецификации, может существенно сократить длину теста, если такие последовательности достаточно короткие. Более того, при описании современных систем часто приходится учитывать опциональность неформальной спецификации, и соответственно, использовать методы синтеза тестов для недетерминированных автоматов; последнее в большинстве случаев повышает длину тестов. Адаптивные различающие последовательности существуют чаще, чем безусловные, и, как правило, имеют меньшую длину, что делает их выбор более предпочтительным для синтеза тестов. В настоящей работе мы исследуем свойства адаптивных различающих последовательностей и оптимизируем метод построения таковых для полностью определённых, возможно, недетерминированных конечных автоматов. Предложенный подход основан на ограничении размеров различающего автомата, по которому строится различающий тестовый пример, служащий удобной формой представления адаптивной различающей последовательности. Проведённые эксперименты позволили оценить длину и вероятность существования адаптивных различающих последовательностей для случайно сгенерированных автоматов с различной степенью недетерминизма. Также в работе рассмотрен специальный класс так называемых автоматов без слияний, которые описывают широкий класс реальных систем и обладают «хорошими» для синтеза тестов свойствами; в частности, для таких автоматов практически всегда существуют адаптивные различающие последовательности, если для каждой пары «состояние, входной символ» существует не более трех различных переходов, т.е. степень недетерминизма в автомате не больше трех.
653			_aконечные автоматы
653			_aтестовые примеры
653			_aадаптивные различающие последовательности
655		4	_aстатьи в журналах _9745982
700	1		_aЕвтушенко, Нина Владимировна _970064
773	0		_tТруды Института системного программирования РАН _d2018 _gТ. 30, вып. 4. С. 139-154 _x2079-8156
852	4		_aRU-ToGU
856	7		_uhttp://vital.lib.tsu.ru/vital/access/manager/Repository/vtls:000646097
908			_aстатья
999			_c508989