Твердість і невідповідність мінімізації адаптивних відмінних послідовностей

Анотація

Адаптивна розрізнювальна послідовність (ADS) може бути використана для ідентифікації невідомого початкового стану кінцевого автомата (FSM). Вже давно відомо, що перевірка існування ADS для FSM та пошук ADS для FSM, коли такий існує, можна виконати за поліноміальний час. Однак проблема пошуку мінімальної ADS досі не вивчалася. Формування мінімальної ADS особливо мотивоване, коли така ADS використовується неодноразово, наприклад для побудови тестової послідовності. Ми вводимо ряд метрик, щоб визначити мінімум ADS і показати, що проблема генерації мінімуму ADS щодо цих метрик є NP-повною. Крім того, ми надаємо результати невідповідності для цих складних проблем і показуємо, що не лише прийняття рішення, але й наближення такого мінімального рівня ADS є важкою проблемою. Ми модифікуємо єдиний існуючий алгоритм генерування ADS з поліноміальним часом і експериментально показуємо, що ці модифікації створюють зменшені ADS. Ми також перевіряємо мотивацію мінімізації ADS, представляючи експериментальні результати щодо ефекту використання зменшених ADS для генерації тестових послідовностей.

Це попередній перегляд вмісту передплати, увійдіть, щоб перевірити доступ.

Параметри доступу

Придбайте одну статтю

Миттєвий доступ до повної статті PDF.

Розрахунок податку буде завершено під час оформлення замовлення.

Підпишіться на журнал

Негайний онлайн-доступ до всіх випусків з 2019 року. Підписка буде автоматично поновлюватися щороку.

Розрахунок податку буде завершено під час оформлення замовлення.