Approximation Completeness of Linear Definite Automata

Moldovanov Ilia Vladimirovich

Approximation Completeness of Linear Definite Automata

Moldovanov I. V.

Moldovanov Ilia Vladimirovich

graduate student, Lomonosov Moscow State University, Faculty of Mechanics and Mathematics, Chair of Mathematical Theory of Intellectual Systems

Received: 25 Mar 2026

Published: 2025, vol. 29, issue 4, pp. 135–149

Download full text (In Russian)

Abstract

In linear definite automata, the output signals at each moment depend only on a bounded number of the most recent input values.

This paper studies functional completeness with respect to the operator of approximation closure for the class of linear definite automata over the two-element field. For this class of automata, a completeness criterion is obtained, formulated in terms of a system of precomplete classes.

Keywords: approximation closure, linear automata, definite automata

BibTeX

@article{IS-Moldovanov2025,
  author  = {Moldovanov, Ilia Vladimirovich},
  title   = {{Approximation Completeness of Linear Definite Automata}},
  journal = {Intelligent Systems. Theory and Applications},
  year    = {2025},
  volume  = {29},
  number  = {4},
  pages   = {135--149},
}

AMSBIB

\Bibitem{IS-Moldovanov2025}
\by I.\,V.~Moldovanov
\paper Approximation Completeness of Linear Definite Automata
\jour Intelligent Systems. Theory and Applications
\yr 2025
\vol 29
\issue 4
\pages 135--149
\lang In Russian

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

← Back to issue