Post-Kalkül

Eine Menge von Regeln, durch die bestimmte Zeichenketten in neue Zeichenketten umgewandelt werden können, ist die Grundlage aller mathematischen oder logischen Systeme. Der Post-Kalkül verwendet Substitutionsregeln, die beidseitig aus einer Folge von Variablen und Konstanten bestehen. Die übrigen wortverarbeitenden Kalküle definieren weniger allgemeine Regeln zur Substitution. Der Kanonische Post-Kalkül besitzt nachfolgende Form.

u₁V₁u₂V₂ … u_mV_mu_m+1 → w₁V'₁w₂V'₂ … w_nV'_nw_n+1

V₁, V₂ … V_m sind Variablen, es gilt {V'₁...V'_n} ⊆ {V₁...V_n}

u₁, u₂ … u_m, u_m+1, w₁, w₂ … w_m, w_m+1 sind Teilworte des Ausgangswortes

Dabei gibt der Index m die Variablenanzahl auf der linken Regelseite und n die Variablenanzahl auf der rechten Regelseite an. Die Variablen der rechten Regelseite stellen eine Teilmenge der linken Regelseite dar. Die Reihenfolge der Variablen der rechten Regelseite darf sich von der Reihenfolge der linken Regelseite unterscheiden. Darüber hinaus kann jede Variable der linken Regelseite, mehr als einmal auf die rechte Regelseite übertragen werden (n >= m). Es darf eine unbegrenzte Anzahl an Variablen genutzt werden. Alle definierten Regeln werden stets auf das gesamte Ausgangswort angewendet.

Der Kanonische Post-Kalkül ist ein nichtdeterministischer Kalkül und besitzt die nachfolgenden Eigenschaften.

• Bei Verarbeitung eines Eingabewortes werden alle anwendbaren Regeln parallel angewendet.
• Die Ergebnisse der nichtdeterministischen Verarbeitung werden in einer Baumstruktur abgelegt.
• Beim Pattern Matching kann es mehrere Möglichkeiten für die Variablenbelegung geben.
• Die Verarbeitung eines Teilbaumes wird beendet, sobald keine Regel mehr auf ihn anwendbar ist.
• Kann keiner der Teilbäume weiter bearbeitet werden, so ist die Verarbeitung des Eingebewortes beendet.

Eingabewort

possibility

Regeln

R1 po[A]s[B]ibility → [B]foo[A]

R2 po[A]i[B]i[C]y → [A][C]bar[B]xorize

R3 s[A]o[B] → foos

Tabelle

Baum

      ┌─────────────┐
  L0  │ possibility │
      └──────┬──────┘
             │↓
          ┌──┴─────┬───────────────┬────────────────────┐
          │        │               │                    │
          │ R1     │ R1            │ R2                 │ R2
          │↓       │↓              │↓                   │↓
      ┌───┴──┐  ┌──┴───┐  ┌────────┴────────┐  ┌────────┴────────┐
  L1  │ foos │  │ sfoo │  │ sstbarbilxorize │  │ sstbarbilxorize │
      └──────┘  └──┬───┘  └────────┬────────┘  └────────┬────────┘
                   │               │                    │
                   │ R3            │ R3                 │ R3
                   │               │                    │
                   └───────────────┼────────────────────┘
                                   │↓
                               ┌───┴──┐
  L2                           │ foos │
                               └──────┘

• Semi-Thue-System
• Markow-Algorithmus

• Post-Kalkül Interpreter (englisch)