English Russian
Izvestiya of Altai State
University Journal
The News of Altai State University

 Архив журнала «Известия АлтГУ», начиная с 2017 г., размещен на новой версии сайта http://izvestiya.asu.ru
 Актуальная информация о журнале размещена на новой версии сайта http://izvestiya.asu.ru

Print ISSN 1561-9443
On-line ISSN 1561-9451
Issues list
Table of Contents
Physical science
About the Journal
Editorial board and Editorial advisory board
Regulations on reviewing research papers
Rules of the articles representation
Publication Ethics of the journal «Izvestiya of Altai State University»

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 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

Key words: Moore finite automata, logical network, inference of a word in the Baer calculus

Full text at PDF, 802Kb. Language: Russian.

Altai State University (Barnaul, Russia)
E-mail: ganov-math.asu.ru@mail.ru

Polzunov Altai State Technical University (Barnaul, Russia)
E-mail: docentdegtereva@gmail.com


Print Edition of "Izvestiya of Altai State University" © 1996-2017 Altai State University.
All rights reserved. Any of parts of a journal or edition as a whole cannot be reprinted without the written sanction of the authors or publisher. On purchase of a journal to address to ASU publishing house:
Altai State University. 656049, 66 Dimitrova street, Barnaul, Russia. Telephone + 7 (3852) 366351.