Post-Kalkül

Der vom polnisch-US-amerikanischen Mathematiker Emil Leon Post entwickelte Post-Kalkül zählt zu den Wortverarbeitenden Kalkülen. Diese beschreiben, wie durch formale Umwandlung von Zeichenketten, ein bestimmtes Ergebnis erzielt werden kann. Eine Kenntnis über die spezifischen Bedeutung der Zeichenkette ist hierbei unnötig.

Definition und Funktionsweise

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₂ ... Z_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.

Einfaches Fallbeispiel

• 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

  Eingabewort     | [A]       | [B]  | [C] | Ausgabewort     | Regel | Level
  ----------------+-----------+------+-----+-----------------+-------+------
  possibility     | s         | /    | /   | foos            |    R1 |    L0
   "              | /         | s    | /   | sfoo            |    R1 |    L0
   "              | ssib      | l    | t   | ssibtbarlxorize |    R2 |    L0
   "              | ss        | bil  | t   | sstbarbilxorize |    R2 |    L0
   "              | ss        | b    | lit | sslitbarbxorize |    R2 |    L0
  ----------------+-----------+------+-----+-----------------+-------+------
  sfoo            | fo        | /    | /   | foos            |    R3 |    L1
   "              | f         | o    | /   | foos            |    R3 |    L1
  ssibtbarlxorize | sibtbarlx | rize | /   | foos            |    R3 |    L1
  sstbarbilxorize | stbarbilx | rize | /   | foos            |    R3 |    L1
  sslitbarbxorize | slitbarbx | rize | /   | foos            |    R3 |    L1

• BAUM

  /-------------\
  | possibility |                                                         L0
  \-------+-----/
          |
          V
     /----------+----- .. -----+---------------------\
     |          |              |                     |
     | R1       | R1           | R2                  | R2
     |          |              |                     |
     V          V              V                     V
  /------\   /------\       /-----------------\   /-----------------\
  | foos |   | sfoo |       | sstbarbilxorize |   | sslitbarbxorize |     L1
  \------/   \--+---/       \--+--------------/   \--+--------------/
                |              |                     |
                | R3           | R3                  | R3
                |              |                     |
                \------ .. ----+---------------------/
                               |
                               V
                            /------\
                            | foos |                                      L2
                            \------/

Anwendungsbeispiele

Addition von Unärzahlen

• Eingabewort

||||||+||||||||+|+||

• Regel

[A]+[B]->[A][B]

• Ergebnis

|||||||||||||||||

Subtraktion von Unärzahlen

• Eingabewort

|||||-|||

• Regeln

[A]|-[B]|->[A]-[B]

[A]-->[A]

• Ergebnis

||

Multiplikation von Unärzahlen

• Eingabewort

|||*||||=

• Regeln

|[A]*[B]=[C]->[A]*[B]=[C][B]

• [A]=[B]->[B]

• Ergebnis

||||||||||||

Parität prüfen

• Eingabewort

101010

• Regeln

[A]00[B]->[A]0[B]

[A]01[B]->[A]1[B]

[A]10[B]->[A]1[B]

[A]11[B]->[A]0[B]

• Ergebnis

1

Siehe auch

• Semi-Thue-System
• Markow-Algorithmus

Weblinks

• Post-Kalkül Interpreter (englisch)