Izvestiya of Saratov University.

Mathematics. Mechanics. Informatics

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

For citation:

Mangusheva I. P. Morphismes Based on Compatible Tolerances of Finite Automata. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2008, vol. 8, iss. 4, pp. 80-90. DOI: 10.18500/1816-9791-2008-8-4-80-90

This is an open access article distributed under the terms of Creative Commons Attribution 4.0 International License (CC-BY 4.0).
Published online: 
17.11.2008
Full text:
download
(downloads: 170)
Language: 
Russian
Heading: 
Computer Sciences
UDC: 
519.95
DOI: 
10.18500/1816-9791-2008-8-4-80-90

Morphismes Based on Compatible Tolerances of Finite Automata

Autors: 
Mangusheva Irina Pavlovna, Saratov State University
Abstract: 

It is suggested a method of a construction with the help of some triple of tolerances defined on the sets of states, input and output symbols of an finite definite automaton an another automaton which is connected with the original automaton by a certain morphism. Considered construction generalizes the known method of finding of the homomorphic images of an automaton with the help of a triple of equivalences, which satisfies to the certain conditions.

Key words: 
finite determined automaton
homomorphic image
congruence
compatible tolerances
tolerant image
partition
covering
References: 
  1. Богомолов А.М., Салий В.И. Алгебраические основы теории дискретных систем. М.: Наука, физмат. лит., 1997. 368 c.
  2. Шрейдер Ю.А. Равенство, сходство, порядок. М.: На- ука, 1971.
  3. Chajda I. Characterization of Relational Blocks // Algebra universalis. 1980. V. 10. P. 65-69.
  4. Карпов Ю. Г. Теория автоматов. СПб.: Питер, 2003. 208 с.
  5. Hartmanis J., Stearns R. Algebraic Structure Theory of Sequential Machines. N.Y.: Prentice-Hall Inc., 1966. 213 p.
  6. Мангушева И.П. Построение решетки стабильных толерантностей конечного автомата // Методы и системы технической диагностики. Саратов: Изд-во Сарат. ун-та, 1981. Вып. 2. С. 106–112.
  7. Хрусталев П.М. Покрытия и разбиения со свойством подстановки в конечных автоматах // Методы и системы технической диагностики. Саратов: Изд-во Сарат. ун-та, 1981. Вып. 2. C. 96–106.
  8. Дидидзе Ц.Е. О гомоморфизмах автоматов // Тр. ВЦ АН Груз. ССР, 1973. Т. 12, № 1. C. 118–131.
  9. Ильичева И.П., Печенкин В.В. Контроль структурных автоматов по стабильным отношениям // Методы и системы технической диагностики. Саратов: Изд-во Сарат. ун-та, 1985. Вып. 5. С. 35–43.
  • 837 reads