The completeness problem in the class of linear definite automata
Received: 08 Nov 2026 Revised: 09 Nov 2026 Accepted: 10 Nov 2026
Published: 2026, vol. 30, issue 4, pp. 112–116
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)
RU