
12(85) 2015 MATHEMATICS
V. A. Ganov, R. V. Degtereva
Algorithmic Problems and Restrictions on Inference Complexity
In the paper, the authors continue their study of logical nets on the basis of finite automata. A special basis of finite automata and dictionary operators implemented by logical nets on this basis are introduced. Automata programs are associated with inference rules of wellknown Post calculus. The key feature of the Post calculus is that words equivalency problem is algorithmically unsolvable. Therefore, a set of operators implemented by these nets are also algorithmically unsolvable. Then properly constructed logical nets are identified, and only these nets on the basis of finite automata are shown to operate correctly. The inference complexity is defined in the following way: the socalled basic automata are identified that directly simulate inference rules for words in a specific calculus. Then the inference complexity is taken to be equal to the number of automata in the computational model of this inference. It is proved that for fixed restrictions a set of operators implemented by the previously identified nets is algorithmically solvable. Every implemented operator is associated with a word of an alphabet A_{0}, inferred in L_{0}. Therefore, for a given operator with a corresponding word T it is possible to infer the word T by exhausting all possible inferences. If the desired inference is short then in accordance with the Theorem 10 it can be obtained. Otherwise, if the desired inference is too long or nonexistent then the proposed technique will fail.
DOI 10.14258/izvasu(2015)1.217
Key words: Moore finite automata, logical network, inference of a word in the Baer calculus
GANOV V. A.
DEGTEREVA R. V.
