Algorithmic decidability of the completeness problem for finite sets containing the zero constant in the class of definite linear automata
https://doi.org/10.22405/2226-8383-2025-26-5-137-157
Abstract
Determining the completeness of finite subsets is an important task in the study of functional systems. In the class of finite automata with composition operations, the problem of checking the completeness of finite subsets is algorithmically undecidable. Conversely, in the class of finite automata with superposition operations, no finite complete systems exist. The subclass of definite automata is notable for having finite complete systems with respect to superposition operations; however, the problem of verifying the completeness of finite subsets in this case is also algorithmically undecidable. Previously, the class of linear automata with composition operations was studied, and an algorithm for determining the completeness of finite subsets was developed for this class. At the same time, it was shown that finite complete systems do not exist in the class of linear automata with superposition operations. Of particular interest is the investigation of this problem in the context of definite linear automata with superposition operations. In this work, an algorithm is proposed for verifying the completeness of finite subsets that include the zero constant in the class of definite linear automata.
About the Author
Ilya Vladimirovich Moldovanov
Lomonosov Moscow State University
Russian Federation
Russian Federation
postgraduate student
References
1. Kratko, M.I. 1964, “Algorithmic undecidability of the completeness recognition problem for finite automata”, Proceedings of the USSR Academy of Sciences, vol. 155, no. 4, pp. 771–774.
2. Buyevich, V.A. 1972, “On the algorithmic undecidability of recognizing A-completeness for O.D.-functions”, Mathematical Notes, vol. 12, no. 6, pp. 687–697.
3. Chasovskikh, A.A. 1991, “On completeness in the class of linear automata”, Mathematical Questions of Cybernetics, no. 3, pp. 140–166.
4. Chasovskikh, A.A. 2018, “The completeness problem in classes of linear automata”, Intelligent Systems: Theory and Applications, pp. 151–153.
5. Chasovskikh, A.A. 2014, “The A-completeness problem of linear-automatic functions over finite fields”, Intelligent Systems: Theory and Applications, vol. 18, no. 1, pp. 253–257.
6. Chasovskikh, A.A. 1986, “On the algorithmic decidability of the completeness problem for linear automata”, Moscow University Bulletin. Series 1: Mathematics, Mechanics, no. 3, pp. 82–84.
7. Chasovskikh, A.A. 2013, “Linear-automatic functions with superposition operations”, Neurocomputers: Development and Application, no. 8, pp. 3–13.
8. Kudryavtsev, V.B., Alekhin, S.V. & Podkolzin, A.S. 1985, Introduction to automata theory, Nauka, Moscow.
9. Buyevich, V.A. & Klindukhova, T.E. 2001, “On the algorithmic undecidability of problems regarding A-completeness and completeness for definitive limited-deterministic functions”, Mathematical Questions of Cybernetics, no. 10, pp. 29–50.
10. Zhuk, D.V. 2008, “On the undecidability of the completeness problem for definitive automata”, Intelligent Systems: Theory and Applications, vol. 12, no. 1, pp. 211–228.
11. Chashkin, A.V. 2007, Lectures on discrete mathematics, [Publisher not specified], Moscow.
12. Lidl, R. & Niederreiter, H. 1988, Finite fields, vols. 1–2, Mir, Moscow.
13. Ireland, K. & Rosen, M. 1987, A classical introduction to modern number theory, Mir, Moscow, 416 p.
14. Chasovskikh, A.A. 2019, “On classes of transfer functions of linear automata”, Intelligent Systems: Theory and Applications, vol. 23, no. 3, pp. 135–142.
15. Gill, A. 1974, Linear sequential machines, Nauka, Moscow, 288 p.
16. Ronzhin, D.V. 2020, “On the conditions for A-completeness of linear automata over binaryrational numbers”, Discrete Mathematics, vol. 32, no. 2, pp. 44–60.
17. Ronzhin, D.V. 2021, “Recognition of A-completeness of finite systems of linear automata with additions over the ring of binary-rational numbers”, Intelligent Systems: Theory and Applications, vol. 25, no. 1, pp. 149–163.
Review
For citations:
Moldovanov I.V. Algorithmic decidability of the completeness problem for finite sets containing the zero constant in the class of definite linear automata. Chebyshevskii Sbornik. 2025;26(5):137-157. (In Russ.) https://doi.org/10.22405/2226-8383-2025-26-5-137-157
Views:
35
JATS XML
Email this article 