On the completeness of systems of finite automata

V. A. Orlov


Abstract: For an arbitrary alphabet $A$, we construct a recursive set of bases of automata with a single output and no more than two inputs, with algorithmically unsolvable completeness problem. The result is final, because the bases of automata with a single input and single output are incomplete.

UDC: 519.10

Received: 15.06.1994

DOI: 10.4213/dm474

 English version: Discrete Mathematics and Applications, 1997, 7:3, 273–277

Bibliographic databases:

• 
•