Izvestiya of Saratov University.

Mathematics. Mechanics. Informatics

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


For citation:

Mangusheva I. P. Ordered automata and tolerant images of FDA. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2013, vol. 13, iss. 2, pp. 91-99. DOI: 10.18500/1816-9791-2013-13-2-1-91-99, EDN: SJJAZX

This is an open access article distributed under the terms of Creative Commons Attribution 4.0 International License (CC-BY 4.0).
Published online: 
27.02.2013
Full text:
(downloads: 202)
Language: 
Russian
Heading: 
UDC: 
519.95
EDN: 
SJJAZX

Ordered automata and tolerant images of FDA

Autors: 
Mangusheva Irina Pavlovna, Saratov State University
Abstract: 

Finite deterministic automaton (FDA) with partially ordered (an ordered automaton) sets of states, input and output symbols is described in the article. The mapping of FDA on an ordered automaton, which is named "p-morphism" is defined. It is shown that so called tolerant images, which are constructed with the help of compatible tolerances on the set of states of FDA, are particular case of ordered automata, which are connected with the original automaton by a p-morphism. Necessary and sufficient conditions are defined, under which an ordered automaton is a tolerant image of the original one. 

References: 
  1. Mangusheva I. P. Morphismes based on compatible tolerances of finite automata. Izv. Sarat. Universiteta. N. S. Ser. Math. Mech. Inform., 2008, vol. 8, iss. 4, pp. 80–90 (in Russian).
  2. Bogomolov A. M., Saliy V. N. Algebraicheskie osnovy teorii diskretnykh sistem [Algebraic foundations of the theory of discrete systems]. Moscow, Nauka, 1997. 368 p. (in Russian). 3. Karpov U. G. Teoriia avtomatov [Automata theory]. St. Petersburg, Piter, 2003, 208 p. (in Russian).
Received: 
07.09.2012
Accepted: 
14.01.2013
Published: 
27.02.2013
Short text (in English):
(downloads: 111)