|
Fundamentalnaya i Prikladnaya Matematika, 2009, Volume 15, Issue 3, Pages 33–47
(Mi fpm1227)
|
|
|
|
This article is cited in 2 scientific papers (total in 2 papers)
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
Abstract:
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.
Citation:
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
Linking options:
https://www.mathnet.ru/eng/fpm1227 https://www.mathnet.ru/eng/fpm/v15/i3/p33
|
Statistics & downloads: |
Abstract page: | 327 | Full-text PDF : | 134 | References: | 60 | First page: | 1 |
|