Intelligent Systems.
Theory and Applications

(Intellektual'nye Sistemy. Teoriya i Prilozheniya)

The completeness problem in the class of linear definite automata

Abstract

This work studies completeness problems in the class of linear definite automata over the two-element field. Reduced criterial systems of closed classes are described for approximation completeness and completeness under superposition. These criteria are also used to establish the algorithmic decidability of both completeness problems for finite systems.

Keywords: linear definite automata, approximation completeness, superposition.

BibTeX
@article{IS-Moldovanov2026,
  author  = {Moldovanov, Ilia Vladimirovich},
  title   = {{The completeness problem in the class of linear definite automata}},
  journal = {Intelligent Systems. Theory and Applications},
  year    = {2026},
  volume  = {30},
  number  = {4},
  pages   = {112--116},
}
AMSBIB
\Bibitem{IS-Moldovanov2026}
\by I.\,V.~Moldovanov
\paper The completeness problem in the class of linear definite automata
\jour Intelligent Systems. Theory and Applications
\yr 2026
\vol 30
\issue 4
\pages 112--116
\lang In Russian
Published under Creative Commons Attribution 4.0 International (CC BY 4.0)

← Back to issue

× Issue cover