RUS  ENG
Full version
JOURNALS // Izvestiya of Saratov University. Mathematics. Mechanics. Informatics // Archive

Izv. Saratov Univ. Math. Mech. Inform., 2013 Volume 13, Issue 2(1), Pages 91–99 (Mi isu401)

Computer science

Ordered automata and tolerant images of FDA

I. P. Mangusheva

Saratov State University, Russia, 410012, Saratov, Astrahanskaya str., 83

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.

Key words: finite deterministic automaton, tolerant image, ordered automaton, compatible tolerance, covering, partial order.

UDC: 519.95

DOI: 10.18500/1816-9791-2013-13-2-1-91-99



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025