RUS  ENG
Full version
JOURNALS // Matematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography] // Archive

Mat. Vopr. Kriptogr., 2011 Volume 2, Issue 3, Pages 31–46 (Mi mvk35)

On the homomorphisms of strongly connected finite automata into substitution automata

I. A. Kruglov

LLC Certification Research Center, Moscow

Abstract: An approach to a description of homomorphisms of strongly connected finite automata into substitution automata is suggested. This approach is based on special homomorphisms such that their composition with homomorphism of an automaton considered into substitution automaton preserves the group of an image. By means of this approach for strongly connected automata a criterion is given for the existence of nontrivial substitutional homomorphic image wish commutative partial transition functions.

Key words: finite automata, homomorphism.

UDC: 519.713.1

Received 10.V.2011

DOI: 10.4213/mvk35



© Steklov Math. Inst. of RAS, 2024