Analysis and synthesis of abstract automata

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

Fundamentalʹnaâ i prikladnaâ matematika, Tome 15 (2009) no. 4, pp. 101-175.

Résumé

This review contains some final results of research in the area of analysis and synthesis of finite automata by their behavior.

Bibliographie

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

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

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

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

[5] Bogomolov S. A., O vosstanovlenii avtomatov po ikh sledam, Avtoreferat dis. ... kand. fiz.-mat. nauk, M., 1986

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

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

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

[9] Buevich V. A., Kalandarashvili 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

[10] Buevich V. A., Kalandarashvili N. G., Tal A. A., Konechnye avtomaty – ekvivalentnost i povedenie, Nauka, M., 1984 | MR

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

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

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

[14] Grunskii I. S., “Identifikatsiya upravlyayuschikh sistem avtomatnogo tipa”, Tr. mezhdunar. konf. “Matematika v industrii”, ICIM' 98, Taganrog, 1998, 107–109

[15] Grunskii I. S., Analiz povedeniya konechnykh avtomatov, Izd-vo Lugansk. gos. ped. un-ta, Lugansk, 2003

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

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

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

[19] Grunskii I. S., Maksimenko I. I., “O raspoznavanii determinirovannykh avtomatov, zadavaemykh ND-avtomatami”, Tr. III mezhdunar. konf. “Diskretnye modeli v teorii upravlyayuschikh sistem”, Krasnovidovo, 1998, 23–29

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

[21] 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

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

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

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

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

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

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

[28] Kozlovskii V. A., “O raspoznavanii avtomata otnositelno lokalno porozhdënnogo klassa”, DAN SSSR, 285:5 (1981), 1048–1049 | MR

[29] Kozlovskii V. A., O raspoznavanii lokalnykh neispravnostei avtomata, Avtoreferat dis. ... kand. fiz.-mat. nauk, VTs AN SSSR, M., 1981

[30] Kozlovskii V. A., “Lokalnye neispravnosti avtomata i ikh obnaruzhenie”, Matematicheskie voprosy kibernetiki, 3, ed. S. V. Yablonskii, Nauka, M., 1991, 167–186 | MR

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

[32] Kozlovskii V. A., Kopytova O. M., “Predstavleniya avtomatov otnositelno $m$-plotnykh klassov”, Materialy VIII Mezhdunar. sem. “Diskretnaya matematika i eë prilozheniya” (Moskva, 2–6 fevralya 2004 g.), Izd-vo Mosk. un-ta, M., 2004, 277–280

[33] Kon P., Universalnaya algebra, Mir, M., 1968 | MR

[34] Kornoushenko E. K., Diagnostirovanie diskretnykh dinamicheskikh sistem po nakoplennoi informatsii, Avtoreferat dis. ... dokt. tekhn. nauk, IPU, M., 1992

[35] Kornoushenko E. K., “Kontrol logiko-dinamicheskikh sistem po prorezhennoi informatsii”, Izv. RAN. Tekhnicheskaya kibernetika, 1992, no. 1, 171–182 | MR | Zbl

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

[37] Kudryavtsev V. B., Alëshin S. V., Podkolzin A. S., Vvedenie v teoriyu avtomatov, Nauka, M., 1985 | MR | Zbl

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

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

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

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

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

[43] Maksimenko I. I., Eksperimenty v finitno-opredelënnykh metricheskikh prostranstvakh avtomatov, Avtoreferat dis. ... kand. fiz.-mat. nauk, Saratov, 2000

[44] Mur E. F., “Umozritelnye eksperimenty s posledovatelnostnymi mashinami”, Avtomaty, Izd. inostr. lit., M., 1956, 179–210

[45] L. A. Skornyakov (obsch. red.), Obschaya algebra, v. 1, Nauka, M., 1990 | Zbl

[46] P. P. Parkhomenko (red.), Osnovy tekhnicheskoi diagnostiki, Energiya, M., 1976

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

[48] Petrenko A. F., Avtomatnye metody analiza sovmestimosti sredstv vzaimodeistviya v otkrytykh setyakh, Avtoreferat dis. ... dokt. tekhn. nauk, Riga, 1988

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

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

[51] Kharari F., Teoriya grafov, Mir, M., 1973 | MR

[52] Bhattacharyya A., Checking Experiments on Sequential Machines, Wiley, New York, 1989 | Zbl

[53] D. K. Pradhan (ed.), Fault-Tolerant Computing: Theory and Techniques, v. 1, Prentice Hall, Englewood Cliffs, 1986

[54] Hennie F. C., “Fault detecting experiments for sequential circuits”, Proc. 5 Annual Symp. “Switch. Circuits Th. and Logic. Design”, 1964, 95–110

[55] Kohavi Z., Switching and Finite Automata Theory, McGraw Hill, New York, 1970 | MR | Zbl

[56] Kozlovskii V. A., “On the complexity of analyzing experiments for checking local faults of an automaton”, Proc. of the Int. Conf. on FCT' 87, Lect. Notes Comp. Sci., 278, Springer, Berlin, 1987, 259–262 | DOI

[57] Petrenko A. F., Yevtushenko N., Dsouli R., Grey box finite state machine base testing strategies, Publ. No 991, Depart d'informatique et recherch. operat. Univ. de Montreal, 1994