|
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.
Received: 15.06.1994
Citation:
V. A. Orlov, “On the completeness of systems of finite automata”, Diskr. Mat., 9:2 (1997), 74–78; Discrete Math. Appl., 7:3 (1997), 273–277
Linking options:
https://www.mathnet.ru/eng/dm474https://doi.org/10.4213/dm474 https://www.mathnet.ru/eng/dm/v9/i2/p74
|
Statistics & downloads: |
Abstract page: | 435 | Full-text PDF : | 300 | First page: | 1 |
|