zbMATH — the first resource for mathematics

Analysis and synthesis of abstract automata. (English. Russian original) Zbl 1257.68098
J. Math. Sci., New York 169, No. 4, 481-532 (2010); translation from Fundam. Prikl. Mat. 15, No. 4, 101-175 (2009).
Summary: This review contains some final results of research in the area of analysis and synthesis of finite automata by their behavior.

68Q45 Formal languages and automata
68-02 Research exposition (monographs, survey articles) pertaining to computer science
Full Text: DOI
[1] A. V. Aho, J. E. Hopcroft and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading (1974). · Zbl 0326.68005
[2] A. Bhattacharyya, Checking Experiments on Sequential Machines, Wiley, New Delhi (1989). · Zbl 0825.68458
[3] A. M. Bogomolov, A. S. Barashko, and I. S. Grunskii, Experiments on Automata [in Russian], Naukova Dumka, Kiev (1973).
[4] A. M. Bogomolov, I. S. Grunskii, and D. V. Speranskii, Control and Transformations of Discrete Automata [in Russian], Naukova Dumka, Kiev (1975).
[5] A. M. Bogomolov and V. N. Salii, Algebraic Foundations of Discrete System Theory [in Russian], Nauka, Moscow (1997).
[6] S. A. Bogomolov, On Reconstruction of Automata by Their Traces [in Russian], Candidate’s Dissertation in Physics and Mathematics, Moscow (1986).
[7] S. Yu. Borodai, ”Conditional and unconditional experiments on classes of realisations of nondeterministic automata,” in: Abstr. XI Intern. Conf. on Problems of Theoretical Cybernetics [in Russian], Ulyanovsk (1996), pp. 27–28.
[8] S. Yu. Borodai, Experiments in Effectively Determined Classes of Automata [in Russian], Candidate’s Dissertation in Physics and Mathematics, Saratov (1997).
[9] W. Brauer, Automatentheorie. Eine Einf”uhrung in die Theorie endlicher Automaten, Teubner, Stuttgart (1984).
[10] V. A. Buevich, N. G. Kalandarishvili, and A. A. Tal, ”Description of a finite automaton by means of a finite set of input-output sequences,” Autom. Remote Control, No. 199-107 (1970), · Zbl 0208.02105
[11] P. M. Cohn, Universal Algebra, Harper & Row, New York (1965). · Zbl 0141.01002
[12] N. V. Evtushenko, A. V. Lebedev and A. F. Petrenko, ”On checking experiments with nondeterministic automata,” Avtomat. Vychisl. Tekhn., 6, 81–85 (1991).
[13] N. V. Evtushenko and A. Yu. Matrosova, ”On synthesis of control-capable automata networks,” Teknn. Diagnost., 3, 143–152 (1991).
[14] N. V. Evtushenko and A. F. Petrenko, ”On checking capabilities of multiple experiments,” Avtomat. Vychisl. Tekhn., 3, 9–14 (1989).
[15] N. V. Evtushenko and A. F. Petrenko, ”A method of constructing checking experiments for an arbitrary nondeterministic automaton,” Avtomat. Vychisl. Tekhn., 5, 73–76 (1990).
[16] A. Gill, Introduction to the Theory of Finite-State Machines, McGraw-Hill, New York (1962). · Zbl 0158.25801
[17] V. M. Glushkov, ”The abstract theory of automata,” Russ. Math. Surv., 16, No. 5, 1–53 (1961). · Zbl 0104.35404 · doi:10.1070/RM1961v016n05ABEH004112
[18] I. S. Grunskii, ”Identification of control systems of automata type,” in: Proc. ICIM’98 [in Russian], Taganrog (1998), pp. 107–109.
[19] I. S. Grunskii, Analysis of the Behavior of Finite Automata [in Russian], Izd. Lugansk. Gos. Ped. Univ., Lugansk (2003). · Zbl 0374.94034
[20] I. S. Grunskii and V. A. Kozlovskii, Synthesis and Identification of Automata [in Russian], Naukova Dumka, Kiev (2004). · Zbl 1257.68098
[21] I. S. Grunskii, V. A. Kozlovskii, and O. M. Kopytova, ”Representations of automata and analysis of attacks on cryptosystems,” Iskusstv. Intellekt, 4, 764–775 (2004).
[22] I. S. Grunskii, V. A. Kozlovskii, and G. G. Ponomarenko, Representations of Finite Automata by Fragments of Behavior [in Russian], Naukova Dumka, Kiev (1990).
[23] I. S. Grunskii and I. I. Maksimenko, Experiments with Marked Automata [in Russian], Preprint 96.02 Inst. Appl. Math. Mech. Nat. Acad. Sci. Ukraine, Donetsk (1998). · Zbl 0966.68104
[24] I. S. Grunskii and I. I. Maksimenko, ”On recognition of deterministic automata determined by nondeterministic automata,” in: Proc. III Intern. Conf. ”Discrete Models in Control System Theory,” Krasnovidovo [in Russian], Moscow (1998), pp. 23–29.
[25] I. S. Grunskii and I. I. Maksimenko, ”On experiments with automata in the absence of an upper bound on the number of states,” Cybernet. Systems Anal., 35, 563–571 (1999). · Zbl 0966.68104 · doi:10.1007/BF02835853
[26] F. Harary, Graph Theory, Addison-Wesley, Reading (1969).
[27] F. C. Hennie, ”Fault detecting experiments for sequential circuits,” in: Proc. 5th Annual Symp. on Switching Circuit Theory and Logical Design, Princeton Univ., Princeton (1964), pp. 95–110.
[28] N. N. Ivanov, G. I. Mikhailov, V. V. Rudnev and A. A. Tal, Finite Automata: Equivalence and Behavior [in Russian], Nauka, Moscow (1984).
[29] Z. Kohavi, Switching and Finite Automata Theory, McGraw-Hill, New York (1970). · Zbl 0206.47701
[30] E. K. Kornoushenko, Diagnosis of Discrete Dynamic Systems by Accumulated Information [in Russian], Doctoral Dissertation in Techn. Sci., Moscow (1992). · Zbl 0810.93001
[31] E. K. Kornoushenko, ”Monitoring of logic-dynamic systems based on sampled performance data,”J. Comput. System. Sci., 30, No. 6, 107–117 (1992). · Zbl 0810.93001
[32] V. A. Kozlovskii, ”On the structure of the check experiment with an automaton,” Kibernetika, No. 319-23 (1978). · Zbl 0395.68052
[33] V. A. Kozlovskii, On Recognition of Local Faults of an Automaton [in Russian], Candidate’s Dissertation in Physics and Mathematics, Moscow (1981).
[34] V. A. Kozlovskii, ”On the recognition of an automaton relative to a locally generated class,” Sov. Math. Dokl., 23, 626–628 (1981). · Zbl 0541.68034
[35] V. A. Kozlovskii, ”On the complexity of analyzing experiments for checking local faults of an automaton,” in: Proc. of the Int. Conf. on FCT’87, Lect. Notes Comp. Sci., Vol. 278, Springer, Berlin (1987), pp. 259–262.
[36] V. A. Kozlovskii, ”Local faults of an automaton and their detection,” Mat. Vopr. Kibern., 3, 167–186 (1991). · Zbl 0825.68224
[37] V. A. Kozlovskii, ”Representations of group automata,” Cybernet. Systems Anal., 32, 168–172 (1996). · Zbl 0887.68072 · doi:10.1007/BF02366529
[38] V. A. Kozlovskii and O. M. Kopytova, ”Representations of automata relative to m-dense classes,” in: Proc. VIII Intern. Seminar ”Discrete Mathematics and Applications,” Moscow State Univ. [in Russian], Moscow (2004), pp. 277–280.
[39] S. A. Kryvyi and L. E. Matveeva, ”Formal methods for the analysis of the properties of systems,” Cybernet. Systems Anal., 39, 174–191 (2003). · Zbl 1099.68658 · doi:10.1023/A:1024783021463
[40] V. B. Kudryavtsev, S. V. Aleshin, and A. S. Podkolzin, Introduction to Automata [in Russian], Nauka, Moscow (1985). · Zbl 0604.68058
[41] A. B. Kuznetsov and B. A. Trakhtenbrot, ”Investigation of partially recursive operators by means of the Baire space theory,” Dokl. Akad. Nauk SSSR, 105, 897–900 (1955).
[42] B. D. Lukyanov, ”Distinguishing and control experiments with nondeterministic automata,” Cybernet. Systems Anal., 31, 691–696 (1995). · Zbl 0854.68064 · doi:10.1007/BF02366317
[43] B. D. Lukyanov, ”Deterministic realizations of nondeterministic automata,” Cybernet. Systems Anal., 32, 493–504 (1996). · Zbl 0880.68093 · doi:10.1007/BF02366771
[44] I. I. Maksimenko, ”Recognition in effectively determined classes of automata,” Tr. Inst. Prikl. Mat. Mekh. Nac. Akad. Nauk Ukrainy 2, 115–123 (1998).
[45] I. I. Maksimenko, ”Experiments in a class of realizations of nondeterministic automata,” Dokl. NAN Ukrainy, 7, 95–99 (1999). · Zbl 0958.68083
[46] I. I. Maksimenko, Experiments in Finitely Defined Metric Spaces of Automata [in Russian], Candidate’s Dissertation in Physics and Mathematics, Saratov (2000).
[47] E. F. Moore, ”Gedanken-experiments on sequential machines,” Ann. Math. Stud., 34, 129–153 (1956).
[48] P. P. Parkhomenko, ed., Fundamentals of Technical Diagnosis [in Russian], Energiya, Moscow (1976).
[49] A. F. Petrenko, ”Experiments with protocol entities,” Avtomat. Vychisl. Tekhn., 1, 16–21 (1987).
[50] A. F. Petrenko, Automaton Methods of Analysis of the Consistency of Interaction Facilities in Open Networks [in Russian], Doctoral Dissertation in Techn. Sci., Riga (1988).
[51] A. F. Petrenko, N. Yevtushenko, and R. Dssouli, Grey-Box FSM-Based Testing Strategies, Dept. Publ. 991. Dept. IRO, Univ. de Montreal (1994).
[52] D. K. Pradhan, ed., Fault-Tolerant Computing: Theory and Techniques, Vol. 1, Prentice Hall, Upper Saddle River (1986).
[53] L. A. Skornyakov, ed., General Algebra, Vol. 1 [in Russian], Nauka, Moscow (1990). · Zbl 0751.00002
[54] M. A. Spivak, ”On the synthesis of a finite automaton in terms of its set of experiments,” Kibernetika, 5, 15–20 (1969).
[55] B. A. Trakhtenbrot and Ya. M. Barzdin, Finite Automata. Behavior and Synthesis, North-Holland, Amsterdam (1973).
[56] M. P. Vasilevskii, ”The detection of the disrepair of automata,” Kibernetika, No. 493–108 (1973).
[57] V. N. Zakharov, D. A. Pospelov, and V. E. Khazatskii, Control Systems: Specification, Design, Implementation [in Russian], Energiya, Moscow (1972).
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.