This article is cited in 1 scientific paper (total in 1 paper)
On the classification of bases in $P_k$ according to the decidability of the completeness problem for automata
D. N. Babin
M. V. Lomonosov Moscow State University
The completeness problem for bases of the form $\Phi\cup\nu$, where $\Phi\subseteq P_k$ and $\nu$ is a finite system of automaton functions, is considered. Previously, the problem for $k=2$ was solved by the author; it was also shown that there is an algorithm for determining the completeness of the system $\Phi\cup\nu$ when $[\Phi]=P_k$. The article is concerned with the case where $[\Phi]$ is the maximal (precomplete) class in $P_k$. The problem of completeness for systems $\Phi\cup\nu$ is shown to be undecidable if $\Phi$ is embedded in a Slupecki class and algorithmically decidable if $\Phi$ contains the preserving class of all constants. Thus, the bases in $P_k$, $k\ge3$, can be classified according to their ability to guarantee the decidability of the completeness problem for automaton functions.
PDF file (174 kB)
Journal of Mathematical Sciences (New York), 2010, 168:1, 21–31
D. N. Babin, “On the classification of bases in $P_k$ according to the decidability of the completeness problem for automata”, Fundam. Prikl. Mat., 15:3 (2009), 33–47; J. Math. Sci., 168:1 (2010), 21–31
Citation in format AMSBIB
\paper On the classification of bases in $P_k$ according to the decidability of the completeness problem for automata
\jour Fundam. Prikl. Mat.
\jour J. Math. Sci.
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
D. N. Babin, “Solvability of the problem of completeness of automaton basis depending on its boolean part”, Moscow University Mathematics Bulletin, 74:1 (2019), 32–34
|Number of views:|