The completeness problem for linear definite automata

Moldovanov Ilia Vladimirovich

The completeness problem for 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

0009-0004-0595-3350

Received: 26 May 2026 Revised: 03 Jun 2026 Accepted: 05 Jun 2026

Published: 2026, vol. 30, issue 2, pp. 120–141

Download full text (In Russian)

Abstract

This paper studies the completeness problem under superposition in the class of linear definite automata over the finite field with two elements. Its main result is a completeness criterion for arbitrary subsets of linear definite automata, stated in terms of a family of closed classes. This criterion extends earlier results that applied only to finitely generated subsets containing the zero constant. As a consequence, the paper proves that completeness is decidable for finite subsets of the class of linear definite automata.

Keywords: completeness problem, superposition, linear automata, definite automata.

BibTeX

@article{IS-Moldovanov2026,
  author  = {Moldovanov, Ilia Vladimirovich},
  title   = {{The completeness problem for linear definite automata}},
  journal = {Intelligent Systems. Theory and Applications},
  year    = {2026},
  volume  = {30},
  number  = {2},
  pages   = {120--141},
}

AMSBIB

\Bibitem{IS-Moldovanov2026}
\by I.\,V.~Moldovanov
\paper The completeness problem for linear definite automata
\jour Intelligent Systems. Theory and Applications
\yr 2026
\vol 30
\issue 2
\pages 120--141
\lang In Russian

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

← Back to issue