Preview

Труды Института системного программирования РАН

Расширенный поиск

Влияние частичности и адаптивности на сложность задачи идентификации состояний автомата

https://doi.org/10.15514/ISPRAS-2018-30(1)-1

Аннотация

Задача идентификации состояний в конечном автомате была и остается актуальной, поскольку используется во многих приложениях, в частности, при моделировании и тестировании дискретных управляющих систем. Для идентификации текущего состояния системы строятся так называемые установочные и синхронизирующие эксперименты с конечными автоматами, в то время как для идентификации начального состояния системы используются диагностические или различающие эксперименты. Установочные, синхронизирующие, диагностические или различающие эксперименты известны как «умозрительные» эксперименты с конечными автоматами, и методы синтеза входных последовательностей для таких экспериментов (если существуют) в настоящее время определены для недетерминированных и детерминированных, полностью и частично определенных автоматов, описывающих эталонное поведение системы. Известно, что проблема проверки существования и построения установочных, синхронизирующих, диагностических или различающих экспериментов существенно усложняется, если эталонное поведение системы описывается недетерминированным и частичным автоматом, что достаточно часто случается при описании сложных современных систем. Известно также, что в некоторых случаях сложность можно понизить, переключившись на адаптивный (условный) эксперимент с системой. В настоящей работе мы исследуем влияние частичности автомата и адаптивности эксперимента на сложность проверки существования и построения установочных, синхронизирующих, диагностических и различающих экспериментов для детерминированных и недетерминированных автоматов и иллюстрируем соответствующую сложность с использованием подходящих рисунков.

Об авторах

Х. Йенигун
Университет Сабанчи
Турция
Стамбул


Н. Евтушенко
Национальный исследовательский Томский государственный университет; Институт системного программирования им. В.Р. Иванникова РАН; Национальный исследовательский университет Высшая школа экономики
Россия

634050, Томск, пр. Ленина 36

109004, Москва, ул. Солженицына 25

101000, Москва, ул. Мясницкая, д. 20



Н. Кушик
SAMOVAR, CNRS, Телеком Южный Париж/Университет Париж Сакле
Франция
Еври


Х Лопез
SAMOVAR, CNRS, Телеком Южный Париж/Университет Париж Сакле
Франция
Еври


Список литературы

1. Moore E.F. Gedanken-experiments on sequential machines. Automata Studies (Annals of Mathematical Studies), 1956, 1, pp. 129-153.

2. Gill A. State-identification experiments in finite automata. Information and Control, 1961, pp. 132-154.

3. Gill A. Introduction to the Theory of Finite-State Machines. 1962, 207 p.

4. Kohavi Z. Switching and Finite Automata Theory. 1979, 658 p.

5. Sandberg S. Homing and Synchronization Sequences. Lecture Notes in Computer Science, 2005, 3472, pp. 5–33.

6. Lee D., Yannakakis M. Testing Finite-State Machines: State Identification and Verification. IEEE Transactions on Computers, 1994, 43 (3), pp. 306-320.

7. Alur R., Courcoubetis C., Yannakakis, M. Distinguishing tests for nondeterministic and probabilistic machines. Proc. of the 27th ACM Symposium on Theory of Computing, 1995, pp. 363-372.

8. Kushik N., El-Fakih K., Yevtushenko, N. Adaptive homing and distinguishing experiments for nondeterministic finite state machines. Lecture Notes in Computer Science, 2013, 8254, pp. 33-48.

9. Kushik N., Yevtushenko N. On the Length of Homing Sequences for Nondeterministic Finite State Machines. Lecture Notes in Computer Science, 2013, 7982, pp. 220-231.

10. Hierons R.M., Türker U.C. Distinguishing Sequences for Partially Specified FSMs. Lecture Notes in Computer Science, 2014, 8430, pp. 62-76.

11. Yenigün H., Yevtushenko N., Kushik N. Some classes of finite state machines with polynomial length of distinguishing test cases. Proc, of International Symposium on Applied Computing (SAC’2016), 2016, pp. 1680-1685.

12. Kushik N., Yevtushenko N., Yenigun H. Reducing the complexity of checking the existence and derivation of adaptive synchronizing experiments for nondeterministic FSMs. Proc. of Intern. Workshop on Domain Specific Model-based Approaches to Verification and Validation (AMARETTO’2016), 2016, pp. 83-90.

13. Kushik N., El-Fakih K., Yevtushenko N., Cavalli A.R. On adaptive experiments for nondeterministic finite state machines. Software Tools for Technology Transfer, Springer, 2016, 18 (3), pp. 251-264.

14. Yenigun H., Yevtushenko N., Kushik N. The complexity of checking the existence and derivation of adaptive synchronizing experiments for deterministic FSMs. Information Processing Letters, 2017, 127, pp. 49-53.

15. Kushik N. G., Kulyamin V. V., Evtushenko N. V. On the complexity of existence of homing sequences for nondeterministic finite state machines. Programming and Computer Software, 2014, 40(6), pp. 333-336.

16. El-Fakih K., Yevtushenko N., Kushik N. Adaptive distinguishing test cases of nondeterministic finite state machines: test case derivation and length estimation. Formal Asp. Comput., 2018, 30(2), pp. 319-332.

17. N. Kushik, J. López, A. Cavalli, N. Yevtushenko. Improving Protocol Passive Testing through "Gedanken" Experiments with Finite State Machines. In Proceedings of Intern. Conf. on Software Quality, Reliability & Security (QRS’2016), 2016, pp. 315-322.

18. Yenigün H., Kushik N., López J., Yevtushenko N., Cavalli A.R. Decreasing the complexity of deriving tests against nondeterministic finite state machines. Proc. of East-West Design & Test Symposium (EWDTS), 2017, IEEE Xplore, IEEE, pp. 1-4.

19. Hopcroft, J.E., Ullman, J.D. Introduction to Automata Theory, Languages, and Computation (1st ed.), 1979, 521 p.

20. Volkov, M.V. Synchronizing automata preserving a chain of partial orders. Lecture Notes in Computer Science, Vol. 4783, pp. 27–37 (2007)

21. Hibbard T.N. Least Upper Bounds on Minimal Terminal State Experiments for Two Classes of Sequential Machines. J. ACM, 1961, 8(4), pp. 601-612.

22. Pavel V. Martyugin. Careful Synchronization of Partial Automata with Restricted Alphabets. Proceedings of the Intern. Conf. Computer Science in Russia (CSR’2013), 2013, pp. 76-87.

23. Kushik N., Yevtushenko N. Describing Homing and Distinguishing Sequences for Nondeterministic Finite State Machines via Synchronizing Automata. Lecture Notes in Computer Science, 2015, 9223, pp. 188-198.


Рецензия

Для цитирования:


Йенигун Х., Евтушенко Н., Кушик Н., Лопез Х. Влияние частичности и адаптивности на сложность задачи идентификации состояний автомата. Труды Института системного программирования РАН. 2018;30(1):7-24. https://doi.org/10.15514/ISPRAS-2018-30(1)-1

For citation:


Yenigun H., Yevtushenko N., Kushik N., López J. The effect of partiality and adaptivity on the complexity of FSM state identification problems. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2018;30(1):7-24. https://doi.org/10.15514/ISPRAS-2018-30(1)-1



Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)