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.
References
[1]
Aho, A. and Ullman, J. (1973) The Theory of Parsing, Translation, and Compiling. Vol. 1, Prentice Hall, Upper Saddle River.
[2]
Brauer, W. (1984) Automation Theory: An Introduction to the Theory of Finite Automata. Vieweg + Teubner Verlag, Wiesbaden.
[3]
Mateescu, A., Salomaa, A. and Yu, S. (1998) On the Decomposition of Finite Languages. Technical Report 222, Turku Centre for Computer Science, Turku.
[4]
Lallement, G. (1979) Semigroups and Combinatorial Applications. Wiley & Sons, Inc., Hoboken, NJ, 376 p.
[5]
Berstel, J. and Perrin, D. (2008) Theory of Codes. Academic Press, New York, 345 p.
[6]
Mateescu, A., Salomaa, A. and Yu, S. (2002) Factorizations of Languages and Commutativity Conditions. Acta Cybernetica, 15, 339-351.
[7]
Diestel, R. (2005) Graph Theory. 3rd Edition, Springer, Berlin, 421 p.
[8]
Melnikov, B. (2018) Regular Languages and Nondeterministic Finite Automata. RGSU Publ., Moscow. (In Russian)
[9]
Winberg, E.B. (2005) Course of Algebra. Factorial Press, Providence. (In Russian)
[10]
Berstel, J. and Perrin, D. (2005) Codes and Automata. Springer, Berlin, 545 p.
[11]
Melnikov, B. (2017) The Complete Finite Automaton. International Journal of Open Information Technologies, 5, 9-17.
[12]
Melnikov, B. and Dolgov, V. (2022) Simplified Regular Languages and a Special Equivalence Relation on the Class of Regular Languages. Part I. International Journal of Open Information Technologies, 10, 12-20. (In Russian)
[13]
Abramyan, M.E. (2021) Computing the Weight of Subtasks in State Minimization of Nondeterministic Finite Automata by the Branch and Bound Method. University Proceedings. Volga Region. Physical and Mathematical Sciences, 2, 46-52. (In Russian) https://doi.org/10.21685/2072-3040-2021-2-4
[14]
Mora, T. (1994) An Introduction to Commutative and Noncommutative Griibner Bases. Theoretical Computer Science, 134, 131-173.
https://doi.org/10.1016/0304-3975(94)90283-6
