Reconstruction of automata by fragments of behaviour

V. B. Kudryavtsev ; I. S. Grunskii ; V. A. Kozlovskii

Diskretnaya Matematika, Tome 21 (2009) no. 2, pp. 3-42.

Résumé

This survey contains results concerning behavioural and abstract theory of finite automata. Finite automata and related constructions are cornerstone concepts of discrete mathematics and mathematical cybernetics. Automata theory finds multiple applications in programming, technical cybernetics, the theory of dynamic systems, etc. Classical problems of this theory are the direct problems: analysis of processes of information transformation carried out by automata and properties of automata, and the inverse problems: synthesis of automata of prescribed properties and identification (restoring, recognition, deciphering, control and diagnosis) of an automaton by means of experiments with it. The fundamental notion which underlies the study of the above problems is the notion of a fragment which is a natural extension of a great number of known fragments of particular forms possessing their characteristic properties. Another key notion is the notion of an identifier of unobservable components of functioning of an automaton, that is, of a fragment which allows for unambiguous determination of these components. The subject matter reflected in this survey is being developed intensively, both in the direction of solving mathematical problems and in applied studies related to synthesis, testing and verification of complex software and hardware systems. This survey contains a series of final results, but they can be treated as a regular step in studying problems of analysis and synthesis of automata by their behaviour, which are continuously filled with new content and require additional resources to solve them.

Bibliographie

[1] Kon P., Universalnaya algebra, Mir, Moskva, 1968 | MR

[2] Brauer R., Vvedenie v teoriyu konechnykh avtomatov, Radio i svyaz, Moskva, 1987 | MR

[3] Bogomolov A. M., Barashko A. S., Grunskii I. S., Eksperimenty s avtomatami, Naukova dumka, Kiev, 1973 | Zbl

[4] Bogomolov A. M., Grunskii I. S., Speranskii D. V., Kontrol i preobrazovaniya diskretnykh avtomatov, Naukova dumka, Kiev, 1975 | MR | Zbl

[5] Bogomolov A. M., Salii V. N., Algebraicheskie osnovy teorii diskretnykh sistem, Nauka, Moskva, 1997 | MR | Zbl

[6] Grunskii I. S., Kozlovskii V. A., Ponomarenko G. G., Predstavleniya konechnykh avtomatov fragmentami povedeniya, Naukova dumka, Kiev, 1990 | MR

[7] Kudryavtsev V. B., Aleshin S. V., Podkolzin A. S., Vvedenie v teoriyu avtomatov, Nauka, Moskva, 1985 | MR | Zbl

[8] Trakhtenbrot B. A., Barzdin Ya. M., Konechnye avtomaty (povedenie i sintez), Nauka, Moskva, 1970 | MR | Zbl

[9] Kharari F., Teoriya grafov, Mir, Moskva, 1973 | MR

[10] Akho A., Khopkroft Dzh., Ulman Dzh., Postroenie i analiz vychislitelnykh algoritmov, Mir, Moskva, 1979 | MR

[11] Grunskii I. S., Kozlovskii V. A., Sintez i identifikatsiya avtomatov, Naukova dumka, Kiev, 2004

[12] Gill A., Vvedenie v teoriyu konechnykh avtomatov, Nauka, Moskva, 1966 | MR | Zbl

[13] Glushkov V. M., “Abstraktnaya teoriya avtomatov”, Uspekhi matem. nauk, 16:5(101) (1961), 3–62 | MR | Zbl

[14] Mur E. F., “Umozritelnye eksperimenty s posledovatelnostnymi mashinami”, Avtomaty, IL, Moskva, 1956, 179–210

[15] Bhattacharyya A., Checking experiments on sequential machines, Wiley, New Delhi, 1989 | Zbl

[16] Kohavi Z., Switching and finite automata theory, McGraw–Hill, New York, 1970 | MR | Zbl

[17] Maksimenko I. K., Eksperimenty v finitno-opredelennykh metricheskikh prostranstvakh avtomatov, Avtoreferat kand. diss. fiz.-mat. nauk, Saratovskii gosuniversitet, Saratov, 2000

[18] Bogomolov S. A., O vosstanovlenii avtomatov po ikh sledam, Avtoreferat kand. diss. fiz.-mat. nauk, VTs AN SSSR, Moskva, 1986

[19] Spivak M. A., “K sintezu konechnogo avtomata po ego mnozhestvu eksperimentov”, Kibernetika, 1969, no. 5, 15–20 | MR | Zbl

[20] Buevich V. A., Kalandarishvili N. G., Tal A. A., “Ob opisanii konechnogo avtomata s pomoschyu konechnogo mnozhestva vkhod-vykhodnykh slov”, Avtomatika i telemekhanika, 1970, no. 1, 112–122 | MR | Zbl

[21] Ivanov N. N., Mikhailov G. I., Rudnev V. V., Tal A. A., Konechnye avtomaty – ekvivalentnost i povedenie, Nauka, Moskva, 1984 | MR

[22] Grunskii I. S., Analiz povedeniya konechnykh avtomatov, LGPU, Lugansk, 2003

[23] Evtushenko N. V., Lebedev A. V., Petrenko A. F., “O proveryayuschikh eksperimentakh s nedeterminirovannymi avtomatami”, Avtomatika i vychislitelnaya tekhnika, 1991, no. 6, 81–85

[24] Lukyanov B. D., “O razlichayuschikh i kontrolnykh eksperimentakh s nedeterminirovannymi avtomatami”, Kibernetika i sistemnyi analiz, 1995, no. 5, 69–76 | MR

[25] Lukyanov B. D., “Determinirovannye realizatsii nedeterminirovannykh avtomatov”, Kibernetika i sistemnyi analiz, 1996, no. 4, 34–50 | MR

[26] Skornyakov L. A., Obschaya algebra, T. 1, Nauka, Moskva, 1990 | Zbl

[27] Petrenko A. F., Avtomatnye metody analiza sovmestimosti sredstv vzaimodeistviya v otkrytykh setyakh, Avtoreferat dokt. diss. tekhn. nauk, IEP Latviiskoi SSR, Riga, 1988

[28] Petrenko A. F., “Eksperimenty nad protokolnymi ob'ektami”, Avtomatika i vychislitelnaya tekhnika, 1987, no. 1, 16–21

[29] Petrenko A. F., Yevtushenko N., Dssouli R., Grey-box FSM-based testing strategies, Dept. Publ. No 991, Dept. IRO, Univ. de Montreal, 1994

[30] Zakharov V. N., Pospelov D. A., Khazatskii V. E., Sistemy upravleniya. Zadanie. Proektirovanie. Realizatsiya, Energiya, Moskva, 1972

[31] Kryvyi S. A., Matveeva L. E., “Formalnye metody analiza svoistv sistem”, Kibernetika i sistemnyi analiz, 2003, no. 2, 15–36 | MR | Zbl

[32] Parkhomenko P. P., Osnovy tekhnicheskoi diagnostiki, Energiya, Moskva, 1976

[33] Pradhan D. K. (ed.), Fault-tolerant computing: Theory and techniques, Vol. 1, Prentice Hall, Upper Saddle River, NJ, 1986

[34] Kornoushenko E. K., “Monitoring of logic-dynamic systems based on sampled performance data”, J. Comput. Syst. Sci. Int., 30:6 (1992), 107–117 | MR | Zbl

[35] Hennie F. C., “Fault detecting experiments for sequential circuits”, Proc. 5th Annual Symp. on Switching Circuit Theory and Logical Design, Princeton Univ., Princeton, NJ, 1964, 95–110

[36] Vasilevskii M. P., “O raspoznavanii neispravnostei avtomata”, Kibernetika, 1973, no. 4, 93–108 | MR

[37] Borodai S. Yu., Eksperimenty v effektivno zadannykh klassakh avtomatov, Avtoreferat kand. diss. fiz.-mat. nauk, SGU, Saratov, 1997

[38] Borodai S. Yu., “Uslovnye i bezuslovnye eksperimenty s klassami realizatsii ND-avtomatov”, Tezisy dokl. KhI Mezhd. konf. po problemam teor. kibernetiki, SVNTs, Ulyanovsk, 1996, 27–28

[39] Kuznetsov A. B., Trakhtenbrot B. A., “Issledovanie chastichno rekursivnykh operatorov sredstvami teorii berovskogo prostranstva”, Doklady AN SSSR, 105:5 (1955), 897–900 | Zbl

[40] Maksimenko I. I., “Raspoznavanie v effektivno-zadannykh klassakh avtomatov”, Trudy IPMM NAN Ukrainy, 2, 1998, 115–123 | MR

[41] Kornoushenko E. K., Diagnostirovanie diskretnykh dinamicheskikh sistem po nakoplennoi informatsii, Avtoreferat dokt. diss. tekhn. nauk, IPU, Moskva, 1992

[42] Kozlovskii V. A., “O raspoznavanii avtomata otnositelno lokalno porozhdennogo klassa”, Doklady AN SSSR, 258:5 (1981), 1047–1049 | MR

[43] Kozlovskii V. A., O raspoznavanii lokalnykh neispravnostei avtomata, Avtoreferat kand. diss. fiz.-mat. nauk, VTs AN SSSR, Moskva, 1981

[44] Kozlovskii V. A., “Lokalnye neispravnosti avtomata i ikh obnaruzhenie”, Matem. voprosy kibern., 3, 1991, 167–186 | MR

[45] Kozlovskii V. A., Kopytova O. M., “Predstavleniya avtomatov otnositelno $m$-plotnykh klassov”, Materialy VIII Mezhd. Seminara “Diskretnaya matematika i ee prilozheniya”, MGU, Moskva, 2004, 277–280

[46] Kozlovskii V. A., “O predstavleniyakh gruppovykh avtomatov”, Kibernetika i sistemnyi analiz, 1996, no. 2, 21–28 | MR

[47] Kozlovskii V. A., “O strukture kontrolnykh eksperimentov s avtomatom”, Kibernetika, 1978, no. 3, 19–33 | MR

[48] Kozlovskii V. A., “On the complexity of analyzing experiments for checking local faults of an automaton”, Lecture Notes Computer Sci., 278, 1987, 259–262

[49] Grunskii I. S., Kozlovskii V. A., Kopytova O. M., “Predstavleniya avtomatov i analiz atak na kriptosistemy”, Iskusstvennyi intellekt, 2004, no. 4, 764–775

[50] Evtushenko N. V., Matrosova A. Yu., “K sintezu kontroleprigodnykh avtomatnykh setei”, Tekhnicheskaya diagnostika, 1991, no. 3, 143–152 | Zbl

[51] Evtushenko N. V., Petrenko A. F., “Metod postroeniya proveryayuschikh eksperimentov dlya proizvolnogo nedeterminirovannogo avtomata”, Avtomatika i vychislitelnaya tekhnika, 1990, no. 5, 73–76

[52] Evtushenko N. V., Petrenko A. F., “O proveryayuschikh vozmozhnostyakh kratnykh eksperimentov”, Avtomatika i vychislitelnaya tekhnika, 1989, no. 3, 9–14

[53] Maksimenko I. I., “Eksperimenty v klasse realizatsii nedeterminirovannykh avtomatov”, Doklady NAN Ukrainy, 1999, no. 7, 95–99 | MR | Zbl

[54] Grunskii I. S., “Identifikatsiya upravlyayuschikh sistem avtomatnogo tipa”, Trudy ICIM' 98, TGPI, Taganrog, 1998, 107–109

[55] Grunskii I. S., Maksimenko I. I., “O raspoznavanii determinirovannykh avtomatov, zadavaemykh ND-avtomatami”, Trudy III Mezhd. Konf. “Diskretnye modeli v teorii upravlyayuschikh sistem” (Krasnovidovo), MGU, Moskva, 1998, 23–29

[56] Grunskii I. S., Maksimenko I. I., Eksperimenty s markirovannymi avtomatami, Preprint 96.02, IPMM NAN Ukrainy, Donetsk, 1998

[57] Grunskii I. S., Maksimenko I. I., “Ob eksperimentakh s avtomatami pri otsutstvii verkhnei otsenki chisla sostoyanii”, Kibernetika i sistemnyi analiz, 1999, no. 4, 59–71 | MR | Zbl

[58] V. B. Kudryavtsev, I. S. Grunskii, V. A. Kozlovskii, “Analiz povedeniya avtomatov”, Diskretnaya matematika, 21:1 (2009), 3–35 | MR