Discrete automata on semilattices

G. P. Agibalov

Prikladnaâ diskretnaâ matematika, no. 2 (2009), pp. 26-49.

Résumé

The theory of discrete automata on semilattices is one of the important achivements of the Tomsk State University scientific School on applied discrete mathematics. It is a comparatively young branch of the science connecting mathematical cybernetics and abstract algeabras. Inside this branch, we have firstly succeeded in formal defining such notions related to the discrete control systems as the dynamic behaviour, the hardware realizability, the adequate model and its accuracy, and also in solving the problems of logical synthesizing such systems with a given dynamic behaviour and with the possibility of hardware realization at the transistor level and of modelling their dynamic behaviour adequately with any given accuracy. The paper is presented on behalf of 50 years jubilee of the School. It is an extended abstract of the same name monograph by the author issued at TSU in 1993 and now being out of access. All the main results obtained in the theory of discrete automata up to that time are presented in the paper.

Bibliographie

[1] Agibalov G. P., “Funktsionalnye sistemy na polureshëtkakh”, Algoritmy resheniya zadach diskretnoi matematiki, 2, Izd-vo Tom. un-ta, Tomsk, 1987, 3–39 | MR

[2] Agibalov G. P., “Functional systems on semilattices”, Fundamentals of Computation Theory, eds. R. G. Bukharaev, O. B. Lupanov, Springer Verlag, Berlin, 1987, 5–9 | MR

[3] Agibalov G. P., “Kvazimonotonnye funktsii i ikh minimizatsiya”, Kibernetika, 1989, no. 2, 111–113 | MR

[4] Agibalov G. P., “Finite automata on partially ordered sets”, Automatic Control, 11th IFAC World Congress Proceedings, V. 3, eds. V. Utkin, U. Jaaksoo, Pergamon Press, Oxford–New York–Seoul–Tokyo, 1991

[5] Agibalov G. P., “K kodirovaniyu polureshëtok i avtomatov na polureshëtkakh”, Diskretnaya matematika, 3:1 (1991), 74–87 | MR | Zbl

[6] Agibalov G. P., Diskretnye avtomaty na polureshëtkakh, Izd-vo Tom. un-ta, Tomsk, 1993, 227 pp. | Zbl

[7] Agibalov G. P., “Adekvatnye modeli polureshëtok, funktsii i avtomatov na polureshëtkakh”, Vestnik Tomskogo gosuniversiteta, 2000, no. 271, Iyun, 118–121

[8] Agibalov G. P., Buzanov V. A., Lipskii V. B., Rumyantsev B. F., “Matematicheskaya model skhem iz elementov s upravlyaemoi provodimostyu”, Avtomatika i telemekhanika, 1982, no. 9, 89–98 | Zbl

[9] Agibalov G. P., Buzanov V. A., Lipskii V. B., Rumyantsev B. F., Logicheskoe proektirovanie pereklyuchatelnykh avtomatov, Izd-vo Tom. un-ta, Tomsk, 1983, 154 pp.

[10] Pankratova I. A., “Realizatsiya funktsii na polureshëtkakh pereklyuchatelnymi skhemami”, Prikladnaya diskretnaya matematika, 2009, no. 2, 50–55

[11] Parvatov N. G., “Funktsionalnaya polnota v zamknutykh klassakh kvazimonotonnykh i monotonnykh trëkhznachnykh funktsii na polureshëtke”, Diskretnyi analiz i issledovanie operatsii. Ser. 1, 10:1 (2003), 61–78 | MR | Zbl

[12] Parvatov N. G., “Teorema o funktsionalnoi polnote v klasse kvazimonotonnykh funktsii na konechnoi polureshëtke”, Diskretnyi analiz i issledovanie operatsii. Ser. 1, 13:3 (2006), 62–82 | MR

[13] Zakrevskii A. D., Algoritmy sinteza diskretnykh avtomatov, Nauka, M., 1971, 512 pp. | MR | Zbl