publication . Article . 2017

Algorithmic Problems and Restrictions on Inference Complexity

Ганов, В.А.; Дегтерева, Р.В.;
Open Access Russian
  • Published: 30 Sep 2017 Journal: Izvestiya of Altai State University (issn: 1561-9451, eissn: 1561-9443, Copyright policy)
  • Publisher: Izvestiya of Altai State University
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 ...
16 references, page 1 of 2

Здесь 37 соотношений, к ним добавлены 14 одно- буквенных соотношений вида ϕ ⇔ ϕ, где ϕ ∈ A .

Допустимые действия относительно этих соотно- шений определяют правила вывода слов в L4.

Определение 2. Cлово Q смежно со словом P от- носительно L4, если Q получается из P в результате одного допустимого действия, обозначение: L4 : P ⊢ Q. При этом соответствующее допустимое действие на- зывается правилом вывода Q из P.

Теорема 1. Если L4 : P ⊢ Q, то L4 : Q ⊢ P.

Теорема 2. Если L4 : P ⊢ Q, то для любого слова R алфавита A0 L4 : RP ⊢ RQ и L4 : PR ⊢ QR.

Определение 3. Пусть γ - буква, не входящая в A , и S является последовательностью слов, разде-

0 ленных буквой γ вида γX1γX2γX3γ…γXkγ. Тогда S назы- вается L4-рядом, если всякий раз, когда слово Xi со- седствует слева со словом Xi+1, то имеет место смежность L4 : Xi ⊢ Xi+1.

Определение 4. Слово Q называется выводимым из P в исчислении L4, если можно построить L4-ряд, соединяющий P с Q. Слова P и Q называются эквива- лентными в L4, если они взаимно выводимы в L4, обо- значение: L4 : P ⇔ Q.

Теорема 3. Если L4 : P ⊢ Q, то L4 : P ⇔ Q.

Теорема 4. Если L4 : P ⇔ Q то L4 : Q ⇔ P.

Теорема 5. Если L4 : P ⇔ Q , то L4 : RP ⇔ RQ и L4 : PR ⇔ QR.

В [1] указаны другие ассоциативные исчисления, но главная особенность L4 в следующем утверждении.

Теорема 6. Множество слов, эквивалентных слову feam в L4 , не является алгоритмически разрешимым.

2. Базис автоматов. Описывается специальный базис C конечных автоматов из [4] и рассматривают- ся логические сети над C, предназначенные для мо- делирования следующей задачи.

Определение 5. Пусть P - слово алфавита A0, и λ(P) обозначает последовательность вида λ(Q) = = μ…μQμμ… , где длина приставки μ…μ рав- на |Q|+1, (здесь |Q| обозначает длину слова Q). Тогда λ(Q) называется ограниченно-детерминированным оператором, определяемым словом P.

16 references, page 1 of 2
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue