APPROXIMATION OF AUTOMATA WITH RESPECT TO THE ANNIHILATION PREDICATE

Elena A. Tolkacheva; Igor I. Kostyrev

Elena A. Tolkacheva Saint Petersburg Electrotechnical University, 5, building 3, st. Professora Popova, 197376, Saint Petersburg, Russi
Igor I. Kostyrev Saint Petersburg Electrotechnical University, 5, building 3, st. Professora Popova, 197376, Saint Petersburg, Russia

Keywords: automaton, recognizability of automata, predicate of annihilation, semigroup, semigroup algebra, homomorphism of semigroups, algorithmic decidability, approximation of semigroups, nite approximation

Abstract

Automata are the most natural mathematical model for systems that may be in different states. The transfer of questions of approximability with respect to the annihilation predicate of the first kind from varieties of semigroups and polybasic structures to automata is connected with the fundamental property of the automaton — its recognizability. Considering a tribasic semigroup distributive algebra as a model of a semigroup automaton, we have shown that as a result of the transition to polybasic structures, the uniformity of the predicate of equality and the annihilation predicate of the first kind disappears. Consequently, the criteria for decidability of the problem of equality and annihilation predicates will be different. The approximability of automata by tribasic semigroup distributive algebras is associated with the algorithmic decidability of the corresponding problems. The question of the algorithmic decidability of the cancellation problem is of special interest. If there exists an algorithm that determines whether one word is zero for the other for any two words.

Author Biographies

Elena A. Tolkacheva, Saint Petersburg Electrotechnical University, 5, building 3, st. Professora Popova, 197376, Saint Petersburg, Russi

PhD, associate professor at the Department of Algorithmic Mathematics, Saint Petersburg Electrotechnical University, eatolkacheva@etu.ru

Igor I. Kostyrev, Saint Petersburg Electrotechnical University, 5, building 3, st. Professora Popova, 197376, Saint Petersburg, Russia

PhD, tutor at the Department of Algorithmic Mathematics, Sain Petersburg Electrotechnical Universitу, ijkwtsp@gmail.com

References

I. I. Kostyrev, “O finitnoi approksimiruemosti mnogoobrazii polugrupp otnositel’no predikata annulirovaniya” [On finite approximability of a semigroup variety with respect to the annihilation predicate], Sovremennaja algebra [Modern algebra], vol. 28, no. 8, Rostov-on-Don, Russia: Legion, 2010, pp. 35–49 (in Russian).

E. S. Ljapin, Semigroup theory and its applications, Saratov, Russia, 1970 (in Russian).

E. A. Tolkacheva, “Approksimatsiya trekhosnovnykh polugruppovykh distributivnykh algebr otnositel’no edinichno ideal’nykh predikatov po vtoroi komponente” [Approximation of tribasic semigroup distributive algebras with respect to unit ideal predicates in the second component], International Algebraic conference dedicated to the memory of D. K. Faddeev, St. Petersburg, 1997, pp. 291–292 (in Russian).

E. A. Tolkacheva, “Approksimatsiya trekhosnovnykh polugruppovykh distributivnykh algebr otnositel’no edinichno ideal’nykh predikatov po tretei komponente” [Approximation of tribasic semigroup distributive algebras with respect to unit ideal predicates in the third component], Sovremennaja algebra [Modern algebra], vol. 22, no. 2, Rostov-on-Don, Russia: Rostov Math Society, 1997, pp. 95–99 (in Russian).

E. A. Tolkacheva, “Approksimiruemost’ trekhosnovnykh polugruppovykh struktur otnositel’no predikata annulirovaniya pervogo roda” [Approximability of tribasic semigroup structures with respect to the annihilation predicate of the first kind], in Proc. the International Conference Mathematics in the modern world, Russia, 2013, pp. 30–31 (in Russian).

S. Eilenberg, Automata, languages and machines, Orlando, FL, USA: Academic Press Inc., 1974.

N. V. Plotnikova, “Sovremennye problemy matematiki i informatiki,” in Proc. Cherepoveckie nauchnye chtenija 2010, Cherepovets, Russia, 2011, pp. 131–134 (in Russian).

P. S. Novikov, Ob algoritmicheskoj nerazreshimosti problemy tozhdestva slov v teorii grupp, Moscow: Izd-vo Akad. nauk SSSR, 1955 (in Russian).