摘要
We investigate decomposition of codes and finite languages. A prime decomposition is a decomposition of a code or languages into a concatenation of nontrivial prime codes or languages. A code is prime if it cannot be decomposed into at least two nontrivial codes as the same for the languages. In the paper, a linear time algorithm is designed, which finds the prime decomposition. If codes or finite languages are presented as given by its minimal deterministic automaton, then from the point of view of abstract algebra and graph theory, this automaton has special properties. The study was conducted using system for computational Discrete Algebra GAP. .
We investigate decomposition of codes and finite languages. A prime decomposition is a decomposition of a code or languages into a concatenation of nontrivial prime codes or languages. A code is prime if it cannot be decomposed into at least two nontrivial codes as the same for the languages. In the paper, a linear time algorithm is designed, which finds the prime decomposition. If codes or finite languages are presented as given by its minimal deterministic automaton, then from the point of view of abstract algebra and graph theory, this automaton has special properties. The study was conducted using system for computational Discrete Algebra GAP. .
作者
Nikolai I. Krainiukov
Mikhail E. Abramyan
Boris F. Melnikov
Nikolai I. Krainiukov;Mikhail E. Abramyan;Boris F. Melnikov(Faculty of Computational Mathematics and Cybernetics, Shenzhen MSU-BIT University, Shenzhen, China;Department of Algebra and Discrete Mathematics, Southern Federal University, Rostov-on-Don, Russian Federation)
