Влияние частичности и адаптивности на сложность задачи идентификации состояний автомата
https://doi.org/10.15514/ISPRAS-2018-30(1)-1
Аннотация
Об авторах
Х. ЙенигунТурция
Стамбул
Н. Евтушенко
Россия
634050, Томск, пр. Ленина 36
109004, Москва, ул. Солженицына 25
101000, Москва, ул. Мясницкая, д. 20
Н. Кушик
Франция
Еври
Х Лопез
Франция
Еври
Список литературы
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