Образец для цитирования:
Молчанов В. А. Представление универсальных планарных автоматов автономными входными сигналами // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2013. Т. 13, вып. 2. С. 31-37. DOI: https://doi.org/10.18500/1816-9791-2013-13-2-2-31-37
Представление универсальных планарных автоматов автономными входными сигналами
Универсальные планарные автоматы являются универсальными притягивающими объектами в категории автоматов, у которых множества состояний и выходных сигналов наделены структурами плоскостей. Основной результат работы показывает, что любой универсальный планарный автомат изоморфен многосортной алгебраической системе, канонически построенной из автономных входных сигналов исходного автомата.
[1]Плоткин Б. И., Гринглаз Л. Я., Гварамия А. А., Элементы алгебраической теории автоматов, Высш. шк., М., 1994, 192 с.; Plotkin B. I., Greenglaz L. Ja., Gvaramija A. A., Algebraic structures in automata and databases theory, World Scientific, Singapore, River Edge, NJ, 1992[2]Simovici Dan A., “On the theory of reduction of semilatticial automata”, An. Sti. ale Univ. “Al. l. Cuza” Din Iasi. (Ser. Nouă). Sec. 1a, 22:1 (1976), 107–110 [3]Гечег Ф., “О произведениях упорядоченных автоматов. I”, Acta Sci. Math., 24:3–4 (1963), 244–250 [Gécseg F., “On products of ordered automata. I”, Acta Sci. Math., 24:3–4 (1963),244–250][4]Гечег Ф., “О произведениях упорядоченных автоматов. II”, Acta Sci. Math., 25:1–2 (1964), 124–128 [Gécseg F., “On products of ordered automata. II”, Acta Sci. Math., 25:1–2 (1964),124–128][5]Eilenberg S., Automata, languages and machines, v. B, Academic Press, N.Y.–San Francisco–London, 1976, 451 pp. [6]Картеси Ф., Введение в конечные геометрии, Наука, М., 1980, 320 с. ; Introduction to finite geometries, North-Holland Publishing Co., Amsterdam, 1976[7]Улам С., Нерешенные математические задачи, Наука, М., 1964, 168 с. ; Ulam S. M., A Collection of Mathematical Problems, Los Alamos Scientific Laboratories, New Mexico, 1960[8]Глускин Л. М., “Полугруппы и кольца эндоморфизмов линейных пространств”, Изв. АН СССР. Сер. мат., 23:6 (1959), 841–870 [Gluskin L. M., “Semigroups and rings of endomorphisms of linear spaces”, Izv. Akad. Nauk SSSR Ser. Mat., 23:6 (1959), 841–870][9]Jonson B., Topics in Universal Algebras, Lecture Notes in Mathematics, Springer Verlag, Berlin–Heidelberg–N.Y., 1972, 220 pp. [10]Konig D., Theorie der endlichen und unendlichen Graphen, Acad. Verlag M. B. H., Leipzig, 1936, 258 pp. [11]Krasner M., “Endotheorie de Galois abstraita”, Algèbre et Théorie des Nombres, Séminaire P. Dubreil, M.-L. Dubreil-Jacotin, L. Lesieur et C. Pisot, 1968/69, 22ieme annee, Fasc. 1, Paris, 1970, Exp. 6, 19 pp. [12]Molchanov V. A., “A universal planar automaton is determined by its semigroup of input symbols”, Semigroup Forum, 82 (2011), 1–9 [13]Молчанов В. А., “Конкретная характеристика универсальных планарных автоматов”, Математика, механика, Cб. науч. тр., 13, Изд-во Сарат. ун-та, Саратов, 2011, 67–69 [Molchanov V. A., “On concrete characterization of universal planar automata”, Mathematics. Mechanics, 13, Saratov Univ. Press, Saratov, 2011, 67–69][14]Молчанов В. А., “Об относительно элементарной определимости класса универсальных планарных автоматов в классе всех полугрупп”, Алгебра и математическая логика, Tез. докл. Междунар. конф., посвящ. 100-летию со дня рождения В. В. Морозова, Изд-во Казанского (Приволжского) федерального ун-та, Казань, 2011, 145–147 [Molchanov V. A., “On relatively elementary definability of the class of universal planar automata in the class of all semigroups”, Modern Problems of Algebra & Mathematical Logic, Proc. of the international conference dedicated to 100-th anniversary of V. V. Morozov and youth school-conf., Kazan, 2011, 145–147][15]Ершов Ю. Л., Проблемы разрешимости и конструктивные модели, Наука, М., 1980, 416 с. [Ershov Yu. L., Problems of decidability and constructive models, Nauka, Moscow, 1980, 416 pp.]
