Algorithmic Problems and Restrictions on Inference Complexity

Article Russian OPEN
Ганов, В.А.; Дегтерева, Р.В.;
(2017)

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... View more
  • References (16)
    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.

  • Metrics
Share - Bookmark