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

Diskr. Mat., 2010 Volume 22, Issue 2, Pages 80–95 (Mi dm1097)

This article is cited in 4 papers

On the classification of Post automaton bases by the decidability of the $A$-completeness property for definite automata

D. N. Zhuk


Abstract: We consider systems of the form $M=F\cup\nu$, where $F$ is some Post class and $\nu$ is a finite system of definite automata. We divide the Post classes into those for which the problem of $A$-completeness of such systems of definite automata is algorithmically decidable and those for which the problem of $A$-completeness is algorithmically undecidable.

UDC: 519.7

Received: 03.02.2010

DOI: 10.4213/dm1097


 English version:
Discrete Mathematics and Applications, 2010, 20:3, 337–355

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025