Речь идет о тестировании программ. Программы запускаются различными способами и проверяется, что во всех этих запусках программы ведут себя так, как положено. Вопрос только в том, что это за способы и как реализовать эти способы (задача проверки работы программы решена куда лучше).
Рассмотрим программу (или компонент программы), поведение которой описывается конечным автоматом. Тогда под "способами" можно понимать запуски, в которых достигаются заданные состояния автомата, переходы в автомате или даже целые пути. Но проблема в том, что размеры автомата огромные. Поэтому состояния автомата группируют согласно некому отношению эквивалентности и полученный автомат называют "обобщенным автоматом". Задача состоит в автоматическом построении таких обобщенных автоматов. Обобщенный автомат не должен стать недетерминированным, если исходный был детерминированным, ну и количество состояний в обобщенном автомате должно-таки позволять проводить тестирование в приемлемые человеческие сроки.
Сложность:
постановка задачи (четко надо понять, какие автоматы называются "обобщенными" и о каком отношении "обобщения" идет речь),
вычислительная сложность (перебор всех разбиений множества состояний автомата)
Комментариев нет:
Отправить комментарий