Normal view
MARC view
К синтезу адаптивных различающих последовательностей для конечных автоматов (Record no. 508989)
[ view plain ]
| 000 -Маркер записи | |
|---|---|
| Контрольное поле постоянной длины | 05225nab a2200313 c 4500 |
| 001 - Контрольный номер | |
| Контрольное поле | vtls000646097 |
| 005 - Дата корректировки | |
| Контрольное поле | 20230123130243.0 |
| 007 - Кодируемые данные (физ. описан.) | |
| Контрольное поле постоянной длины | cr | |
| 008 - Кодируемые данные | |
| Контрольное поле постоянной длины | 181220|2018 ru s c rus d |
| 024 7# - Прочие стандартные номера | |
| Стандартный номер | 10.15514/ISPRAS-2018-30(4)-9 |
| Источник номера | doi |
| 035 ## - Системный контрольный номер | |
| Системный контрольный номер | to000646097 |
| 040 ## - Источник каталогиз. | |
| Служба первич. каталог. | RU-ToGU |
| Код языка каталог. | rus |
| Служба, преобразующая запись | RU-ToGU |
| 100 1# - Автор | |
| Автор | Твардовский, Александр Сергеевич |
| 9 (RLIN) | 97109 |
| 245 10 - Заглавие | |
| Заглавие | К синтезу адаптивных различающих последовательностей для конечных автоматов |
| Ответственность | А. С. Твардовский, Н. В. Евтушенко |
| 246 11 - Заглавие тома/части | |
| Заглавие тома/части | Deriving adaptive distinguishing sequences for finite state machines |
| 504 ## - Библиография | |
| Библиография | Библиогр.: 11 назв. |
| 520 3# - Аннотация | |
| Аннотация | Конечные автоматы широко используются при построении проверяющих тестов для управляющих систем с гарантированной полнотой обнаружения неисправностей. В ряде случаев такие тесты достигают экспоненциальной длины относительно размеров автомата-спецификации, что мотивирует исследования по оптимизации проверяющих тестов. Существование последовательностей, различающих каждую пару состояний в автомате-спецификации, может существенно сократить длину теста, если такие последовательности достаточно короткие. Более того, при описании современных систем часто приходится учитывать опциональность неформальной спецификации, и соответственно, использовать методы синтеза тестов для недетерминированных автоматов; последнее в большинстве случаев повышает длину тестов. Адаптивные различающие последовательности существуют чаще, чем безусловные, и, как правило, имеют меньшую длину, что делает их выбор более предпочтительным для синтеза тестов. В настоящей работе мы исследуем свойства адаптивных различающих последовательностей и оптимизируем метод построения таковых для полностью определённых, возможно, недетерминированных конечных автоматов. Предложенный подход основан на ограничении размеров различающего автомата, по которому строится различающий тестовый пример, служащий удобной формой представления адаптивной различающей последовательности. Проведённые эксперименты позволили оценить длину и вероятность существования адаптивных различающих последовательностей для случайно сгенерированных автоматов с различной степенью недетерминизма. Также в работе рассмотрен специальный класс так называемых автоматов без слияний, которые описывают широкий класс реальных систем и обладают «хорошими» для синтеза тестов свойствами; в частности, для таких автоматов практически всегда существуют адаптивные различающие последовательности, если для каждой пары «состояние, входной символ» существует не более трех различных переходов, т.е. степень недетерминизма в автомате не больше трех. |
| 653 ## - Ключевые слова | |
| Ключевые слова | конечные автоматы |
| 653 ## - Ключевые слова | |
| Ключевые слова | тестовые примеры |
| 653 ## - Ключевые слова | |
| Ключевые слова | адаптивные различающие последовательности |
| 655 #4 - Термин индексирования — жанр/форма | |
| Жанр/форма | статьи в журналах |
| 9 (RLIN) | 745982 |
| 700 1# - Другие авторы | |
| Другие авторы | Евтушенко, Нина Владимировна |
| 9 (RLIN) | 70064 |
| 773 0# - Источник информации | |
| Название источника | Труды Института системного программирования РАН |
| Место и дата издания | 2018 |
| Прочая информация | Т. 30, вып. 4. С. 139-154 |
| ISSN | 2079-8156 |
| 852 4# - Местонахождение единицы хранения | |
| Код организации-хранителя | RU-ToGU |
| 856 7# - Электронный адрес документа | |
| URL | <a href="http://vital.lib.tsu.ru/vital/access/manager/Repository/vtls:000646097">http://vital.lib.tsu.ru/vital/access/manager/Repository/vtls:000646097</a> |
| 908 ## - Параметр входа данных | |
| Параметр входа данных | статья |
| 999 ## - Системные контрольные номера (Koha) | |
| biblionumber (Koha) | 508989 |
No items available.