Izvestiya of Saratov University.

Mathematics. Mechanics. Informatics

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)

For citation:

Molchanov V. A. Representation of universal planar automata by autonomous input signals. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2013, vol. 13, iss. 2, pp. 31-37. DOI: 10.18500/1816-9791-2013-13-2-2-31-37, EDN: RHABIL

This is an open access article distributed under the terms of Creative Commons Attribution 4.0 International License (CC-BY 4.0).
Published online: 
25.05.2013
Full text:
download
(downloads: 166)
Language: 
Russian
Heading: 
Computer Sciences
UDC: 
519.713.2, 512.534
DOI: 
10.18500/1816-9791-2013-13-2-2-31-37
EDN: 
RHABIL

Representation of universal planar automata by autonomous input signals

Autors: 
Molchanov Vladimir Aleksandrovich, Saratov State University
Abstract: 

Universal planar automata are universally attracted objects in the category of automata, whose sets of states and output signals are endowed with structures of planes. The main result of the paper shows that any universal planar automaton is isomorphic to a many-sorted algebraic system canonically constructed from autonomous input signals of the automaton. 

Key words: 
automata
semigroups
planes
many-sorted algebraic systems
References: 
  1. Plotkin B. I., Greenglaz L. Ja., Gvaramija A. A. Algebraic structures in automata and databases theory. Singapore, River Edge, NJ, World Scientific, 1992. (Rus. ed.: Plotkin B. I., Gringlaz L. Ia., Gvaramiia A. A. Elementy algebraicheskoi teorii avtomatov. Moscow, Vysshaia shkola, 1994, 192 p.)
  2. Simovici Dan A. On the theory of reduction of semilatticial automata. An. Sti. ale Univ. «Al. l. Cuza» Din Iasi. (Ser. Nou˘a). Sec. 1a., 1976, vol. 22, no. 1, pp. 107– 110.
  3. G´ecseg F. O proizvedeniiakh uporiadochennykh avtomatov. I [On products of ordered automata. I]. Acta Sci. Math., 1963, vol. 24, no. 3–4, pp. 244–250 (in Russian).
  4. G´ecseg F. O proizvedeniah uporadochennyh avtomatov. II [On products of ordered automata. II]. Acta Sci. Math., 1964, vol. 25, no. 1–2, pp. 124–128 (in Russian).
  5. Eilenberg S. Automata, languages and machines. Vol. B. New York, San Francisco, London, Academic Press, 1976, 451 p.
  6. Introduction to finite geometries. Amsterdam, North- Holland Publishing Co., 1976. (Russ. ed.: Kartesi F. Vvedenie v konechnye geometrii. Moscow, Nauka, 1980, 320 p.)
  7. Ulam S. M. A Collection of Mathematical Problems. New Mexico, Los Alamos Scientific Laboratories, 1960. (Rus. ed.: Ulam S. Nereshennye matematicheskie zadachi. Moscow, Nauka, 1964, 168 p.)
  8. Gluskin L. M. Polugruppy i kol’tsa endomorfizmov lineinykh prostranstv [Semigroups and rings of endomorphisms of linear spaces]. Izv. Akad. Nauk SSSR Ser. Mat., 1959, vol. 23, pp. 841–870 (in Russian). Jonson B. Topics in Universal Algebras. Lecture Notes in Mathematics. Berlin, Heidelberg, New York, Springer Verlag, 1972, 220 p.
  9. Konig D. Theorie der endlichen und unendlichen Graphen. Leipzig, Acad. Verlag M.B.H., 1936, 258 p.
  10. Krasner M. Endotheorie de Galois abstraita. Semin. Dubriel, Dubriel-Jacotin, Lesieur et Pisot. Fac. sci. Paris, 1968–1969(1970), vol. 22, no 1, pp. 6/01-6/19.
  11. Molchanov V. A. A universal planar automaton is determined by its semigroup of input symbols. Semigroup Forum, 2011, vol. 82, pp. 1–9.
  12. Molchanov V. A. Konkretnaia kharakteristika universal’nykh planarnykh avtomatov [On concrete characterization of universal planar automata]. Matematika. Mehanika [Mathematics. Mechanics]. Saratov, Saratov Univ. Press, 2011, iss. 13, pp. 67–69 (in Russian).
  13. Molchanov V. A. On relatively elementary definability of the class of universal planar automata in the class of all semigroups. Algebra i matematicheskaia logika : tez. dokl. Mezhdunar. konf., posviashch. 100-letiiu so dnia rozhdeniia V. V. Morozova [Proc. of the international conference dedicated to 100-th anniversary of V. V. Morozov and youth school-conf. «Modern Problems of Algebra & Mathematical Logic»]. Kazan, 2011, pp. 145–147 (in Russian).
  14. Ershov Yu. L. Problemy razreshimosti i konstruktivnye modeli [Problems of decidability and constructive models]. Moscow, Nauka, 1980, 416 p. (in Russian).
Received: 
25.11.2012
Accepted: 
21.04.2013
Published: 
31.05.2013
Short text (in English):
download
(downloads: 78)
  • 1054 reads