×

The relation between preset distinguishing sequences and synchronizing sequences. (English) Zbl 1342.68184


MSC:

68Q45 Formal languages and automata

Software:

ggplot2; DAAGxtras
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahmad I, Ali FM, Das AS (2004) Lang-algorithm for constructing unique input/output sequences in finite-state machines. IEE Proc Comput Digital Tech 151(2): 131-140 · doi:10.1049/ip-cdt:20040350
[2] ACM/SIGDA benchmark dataset. http://www.cbl.ncsu.edu:16080/benchmarks. Accessed 06 Aug 2013.
[3] Aho AV, Dahbura AT, Lee D, Uyar MU (1988) An optimization technique for protocol conformance test generation based on UIO sequences and Rural Chinese Postman Tours. In: Protocol specification, testing, and verification VIII, Atlantic City. Elsevier, North Holland, pp 75-86
[4] Aho AV, Sethi R, Ullman JD (1986) Compilers: principles, techniques, and tools. Addison-Wesley, Boston
[5] Ananichev DS, Volkov MV (2004) Synchronizing monotonic automata. Theor Comput Sci 327(3): 225-239 · Zbl 1160.68398 · doi:10.1016/j.tcs.2004.03.068
[6] Ananichev DS, Volkov MV (2005) Synchronizing generalized monotonic automata. Theor Comput Sci 330(1): 3-13 · Zbl 1078.68071 · doi:10.1016/j.tcs.2004.09.006
[7] Bogdanov K, Holcombe M, Ipate F, Seed L, Vanak SK (2006) Testing methods for X-machines: a review. Formal Aspects Comput 18(1): 3-30 · Zbl 1103.68461 · doi:10.1007/s00165-005-0085-6
[8] Binder RV (1999) Testing object-oriented systems: models, patterns, and tools. Addison-Wesley, Boston
[9] Broy M, Jonsson B, Katoen J, Leucker M, Pretschner A (eds) (2005) Model-based testing of reactive systems, advanced lectures, Lecture Notes in Computer Science, vol 3472. Springer, Berlin · Zbl 1070.68088
[10] Bochmann Gv, Petrenko A (1994) Protocol testing: review of methods and relevance for software testing. In: ACM international symposium on software testing and analysis, Seattle, pp 109-123 · Zbl 1163.68024
[11] Černý J (1964) A remark on homogeneous experiments with finite automata. Mat -Fyz Časopis Sloven Akad Vied 14: 208-216 · Zbl 0137.01101
[12] Chow TS (1978) Testing software design modeled by finite-state machines. IEEE Trans Softw Eng SE- 4(3): 178-187 · Zbl 0379.68039 · doi:10.1109/TSE.1978.231496
[13] Černý J, Pirická A, Rosenauerová B (1971) On directable automata. Kybernetika 07(4): 289-298 · Zbl 0223.94029
[14] Dorofeeva R, El-Fakih K, Maag S, Cavalli AR, Yevtushenko N (2010) FSM-based conformance testing methods: a survey annotated with experimental evaluation. Inf Softw Technol 52(12): 1286-1297 · doi:10.1016/j.infsof.2010.07.001
[15] Eppstein D (1990) Reset sequences for monotonic automata. SIAM J Comput 19(3): 500-510 · Zbl 0698.68058 · doi:10.1137/0219033
[16] Friedman AD, Menon PR (1971) Fault detection in digital circuits. Computer Applications in Electrical Engineering Series. Prentice-Hall, Englewood Cliffs
[17] Fominykh FM, Volkov MV (2012) P(l)aying for synchronization. In: Moreira and Reis [MR12], pp 159-170 · Zbl 1297.68127
[18] Gerbush M, Heeringa B (2010) Approximating minimum reset sequences. In: Domaratzki M, Salomaa K (eds) CIAA, Lecture Notes in Computer Science, vol 6482. Springer, New York, pp 154-162 · Zbl 1297.68131
[19] Guo Q, Hierons RM, Harman M, Derderian K (2005) Constructing multiple unique input/output sequences using metaheuristic optimisation techniques. In: IEE proceedings software, pp 127-140
[20] Garey MR, Johnson DS (1979) Computers and intractability. W.H. Freeman and Company, New York · Zbl 0411.68039
[21] Gönenç G (1970) A method for the design of fault detection experiments. IEEE Trans Comput C-19(6):551-558 · Zbl 0195.30902
[22] Hennie FC (1964) Fault-detecting experiments for sequential circuits. In: Proceedings of fifth annual symposium on switching circuit theory and logical design. Princeton, New Jersey, pp 95-110
[23] Hierons RM, Jourdan GV, Ural H, Yenigün H (2008) Using adaptive aistinguishing sequences in checking sequence constructions. In: Wainwright RL, Haddad H (eds) SAC. ACM, pp 682-687 · Zbl 1214.68216
[24] Hierons RM, Jourdan GV, Ural H, Yenigün H (2009) Checking sequence construction using adaptive and preset distinguishing sequences. In: Hung DV, Krishnan P (eds) SEFM. IEEE Computer Society, pp 157-166
[25] Holzmann GJ (1991) Design and validation of computer protocols. Prentice Hall, Englewood Cliffs
[26] Harel D, Politi M (1998) Modeling reactive systems with statecharts: the STATEMATE approach. McGraw-Hill, New York
[27] Haydar M, Petrenko A, Sahraoui H (2004) Formal verification of web applications modeled by communicating automata. In: Escrig DF, Núñez M (eds) Formal techniques for networked and distributed systems—FORTE 2004, Lecture Notes in Computer Science, vol 3235. Springer, New York, pp 115-132 · Zbl 1110.68314
[28] ITU-T (1999) Recommendation Z.100 Specification and Description Language (SDL). International Telecommunications Union, Geneva · Zbl 0698.68058
[29] Jourdan GV, Ural H, Yenigun H, Zhang JC (2010) Lower bounds on lengths of checking sequences. Formal Aspects Comput 22(6): 667-679 · Zbl 1214.68216 · doi:10.1007/s00165-009-0135-6
[30] Karp RM (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW (eds) Complexity of computer computations. Plenum Press, New York, pp 85-103 · Zbl 1467.68065
[31] Kushik N, El-Fakih K, Yevtushenko N (2013) Adaptive homing and distinguishing experiments for nondeterministic finite state machines. In: Yenigün H, Yilmaz C, Ulrich A (eds) ICTSS, Lecture Notes in Computer Science, vol 8254. Springer, New York, pp 33-48 · Zbl 1297.68147
[32] Kohavi Z (1978) Switching and finite state automata theory. McGraw-Hill, New York · Zbl 0384.94020
[33] Kudlacik R, Roman A, Wagner H (2012) Effective synchronizing algorithms. Expert Syst Appl 39(14): 11746-11757 · doi:10.1016/j.eswa.2012.04.079
[34] Kushik N, Yevtushenko N (2013) On the length of homing sequences for nondeterministic finite state machines. In: Konstantinidis S (ed) CIAA, Lecture Notes in Computer Science, vol 7982. Springer, New York, pp 220-231 · Zbl 1298.68146
[35] Lai R (2002) A survey of communication protocol testing. J Syst Softw 62(1): 21-46 · doi:10.1016/S0164-1212(01)00132-7
[36] Lee D, Yannakakis M (1994) Testing finite-state machines: state identification and verification. IEEE Trans Comput 43(3): 306-320 · Zbl 1395.68173 · doi:10.1109/12.272431
[37] Lee D, Yannakakis M (1996) Principles and methods of testing finite-state machines—a survey. Proc IEEE 84(8): 1089-1123 · doi:10.1109/5.533956
[38] Martyugin PV (2010) Complexity of problems concerning carefully synchronizing words for PFA and directing words for NFA. In: Ablayev FM, Mayr EW (eds) Computer science—theory and applications, Lecture Notes in Computer Science, vol 6072. Springer, New York, pp 288-302 · Zbl 1285.68089
[39] Martyugin PV (2012) Complexity of problems concerning reset words for cyclic and eulerian automata. Theor Comput Sci 450: 3-9 · Zbl 1279.68163 · doi:10.1016/j.tcs.2012.04.022
[40] Martyugin PV (2012b) Synchronization of automata with one undefined or ambiguous transition. In: Moreira and Reis [MR12], pp 278-288 · Zbl 1297.68157
[41] Martyugin PV (2013) Careful synchronization of partial automata with restricted alphabets. In: Bulatov A, Shur A (eds) Computer science—theory and applications, Lecture Notes in Computer Science, vol 7913. Springer, New York, pp 76-87 · Zbl 1381.68129
[42] Moreira N, Reis R (eds) (2012) Implementation and application of automata—17th international conference, CIAA 2012, Porto. In: Proceedings, Lecture Notes in Computer Science, vol 7381. Springer, New York · Zbl 1246.68050
[43] Naik K (1997) Efficient computation of unique input/output sequences in finite-state machines. IEEE ACM Trans Netw 5(4) · Zbl 0508.68030
[44] Natarajan BK (1986) An algorithmic approach to the automated design of parts orienters. In: 27th Annual symposium on foundations of computer science, pp 132-142 · Zbl 1214.68216
[45] Petrenko A, Yevtushenko N (2005) Testing from partial deterministic FSM specifications. IEEE Trans Comput 54(9): 1154-1165 · doi:10.1109/TC.2005.152
[46] Roman A (2009) Synchronizing finite automata with short reset words. Appl Math Comput 209(1): 125-136 · Zbl 1163.68024 · doi:10.1016/j.amc.2008.06.019
[47] Rabanal P, Rodríguez I, Rubio F (2013) Testing restorable systems: formal definition and heuristic solution based on river formation dynamics. Formal Aspects Comput 25(5): 743-768 · Zbl 1298.68255 · doi:10.1007/s00165-011-0206-3
[48] Rystsov IK (1983) Polynomial complete problems in automata theory. Inf Process Lett 16(3): 147-151 · Zbl 0508.68030 · doi:10.1016/0020-0190(83)90067-4
[49] Rystsov IK (1997) Reset words for commutative and solvable automata. Theor Comput Sci 172(1-2):273-279 · Zbl 0903.68122
[50] Sandberg S (2004) Homing and synchronizing sequences. In: Broy et al. [BJK+05], pp 5-33
[51] Sabnani K, Dahbura A (1988) A protocol test generation procedure. Comput Netw 15(4): 285-297
[52] Stannett M (2006) Simulation testing of automata. Formal Aspects Comput 18(1): 31-41 · Zbl 1103.68593 · doi:10.1007/s00165-005-0080-y
[53] Stowell S (2012) Instant R: an introduction to R for statistical Analysis. Jotunheim Publishing
[54] Teetor P (2011) R Cookbook, 1st edn. O’Reilly
[55] Trahtman AN (2004) Some results of implemented algorithms of synchronization. In: 10th Journees Montoises d’Inform., Liege
[56] Ural H, Williams C (2006) Constructing checking sequences for distributed testing. Formal Aspects Comput 18(1): 84-101 · Zbl 1103.68595 · doi:10.1007/s00165-005-0083-8
[57] Ural H, Zhu K (1993) Optimal length test sequence generation using distinguishing sequences. IEEE/ACM Trans Netw 1(3): 358-371 · doi:10.1109/90.234857
[58] Vasilevskii MP (1973) Failure diagnosis of automata. Cybern Syst Anal 9(4):653-665. doi:10.1007/BF01068590
[59] Vuong ST, Chan WWL, Ito MR (1989) The UIOv-method for protocol test sequence generation. In: The 2nd international workshop on protocol test systems, Berlin
[60] Volkov MV (2008) Synchronizing automata and the cerny conjecture. In: Martín-Vide C, Otto F, Fernau H (eds) LATA, Lecture Notes in Computer Science, vol 5196. Springer, New York, pp 11-27 · Zbl 1156.68466
[61] Wickham H (2009) ggplot2: elegant graphics for data analysis (Use R!), 1st edn, corr. 3rd printing 2010 edition. Springer, New York · Zbl 1170.62004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.