The completeness problem in the class of linear <span
class=

Kalashnikov Maksim Eduardovich

The completeness problem in the class of linear \(p\)-adic automata

Kalashnikov M. E.

Kalashnikov Maksim Eduardovich

Postgraduate student, Chair of Mathematical Theory of Intelligent Systems, Faculty of Mechanics and Mathematics, Lomonosov Moscow State University

Received: 28 Aug 2026 Revised: 30 Aug 2026 Accepted: 01 Sep 2026

Published: 2026, vol. 30, issue 3, pp. 170–188

Download full text (In Russian)

Abstract

The \(K\)-completeness problem in the class of linear \(p\)-adic automata is studied for an odd prime \(p\). Completeness criteria are obtained for homogeneous and inhomogeneous linear \(p\)-adic functions. The results generalize known results for linear \(2\)-adic automata to arbitrary odd prime bases. In addition, a strictly increasing chain of \(K\)-closed classes \(I_\alpha\), \(\alpha \in (0,1]\), of continuum cardinality is constructed.

Keywords: finite automaton, \(p\)-adic number, linear \(p\)-adic automaton, composition operations, feedback, completeness problem, closed class.

BibTeX

@article{IS-Kalashnikov2026,
  author  = {Kalashnikov, Maksim Eduardovich},
  title   = {{The completeness problem in the class of linear \(p\)-adic automata}},
  journal = {Intelligent Systems. Theory and Applications},
  year    = {2026},
  volume  = {30},
  number  = {3},
  pages   = {170--188},
}

AMSBIB

\Bibitem{IS-Kalashnikov2026}
\by M.\,E.~Kalashnikov
\paper The completeness problem in the class of linear \(p\)-adic automata
\jour Intelligent Systems. Theory and Applications
\yr 2026
\vol 30
\issue 3
\pages 170--188
\lang In Russian

Published under Creative Commons Attribution 4.0 International (CC BY 4.0)

← Back to issue