RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 1998 Volume 10, Issue 3, Pages 57–63 (Mi dm430)

This article is cited in 2 papers

Finiteness of the set of automaton Post bases with a decidable completeness problem

D. N. Babin


Abstract: The bases under consideration are those of the form $M=\Phi\cup\nu$, where $\Phi$ is a Post class and $\nu$ is a finite system of automaton functions. It is shown that the sets of Post classes $\Phi$ for which the completeness problem for $\Phi\cup\nu$ is solvable, respectively, the $A$-completeness problem for $\Phi\cup\nu$ is solvable, are finite.

UDC: 519.7

Received: 18.05.1998

DOI: 10.4213/dm430


 English version:
Discrete Mathematics and Applications, 1998, 8:5, 475–482

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024