Algorithmic Problems and Restrictions on Inference Complexity

Abstract

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 well-known 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 so-called 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 A0, inferred in L0. 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 non-existent then the proposed technique will fail.

DOI 10.14258/izvasu(2015)1.2-17