Post calculus

from Wikipedia, the free encyclopedia

The post-calculus developed by the Polish-American mathematician Emil Leon Post is one of the word processing calculi . These describe how a certain result can be achieved through formal conversion of character strings . Knowledge of the specific meaning of the character string is unnecessary here.

Definition and functioning

A set of rules by which certain character strings can be converted into new character strings is the basis of all mathematical or logical systems. The post-calculus uses substitution rules that consist of a sequence of variables and constants on both sides. The other word-processing calculi define less general rules for substitution. The canonical post-calculus has the following form.

u 1 V 1 u 2 V 2 … u m V m u m + 1 → w 1 V ' 1 w 2 V' 2 … w n V ' n w n + 1

V 1 , V 2 … V m are variables, we have {V ' 1 ... V' n } ⊆ {V 1 ... V n }

u 1 , u 2 … u m , u m + 1 , w 1 , w 2 … w m , w m + 1 are partial words of the output word

The index m indicates the number of variables on the left side of the rule and n the number of variables on the right side of the rule. The variables on the right side of the rule represent a subset of the left side of the rule. The order of the variables on the right side of the rule may differ from the order of the left side of the rule. In addition, each variable on the left side of the rule can be transferred more than once to the right side of the rule ( n > = m ). An unlimited number of variables can be used. All defined rules are always applied to the entire source word.

The canonical post-calculus is a nondeterministic calculus and has the following properties.

  • When processing an input word, all applicable rules are applied in parallel.
  • The results of the non-deterministic processing are stored in a tree structure .
  • With pattern matching , there can be several options for assigning variables.
  • Processing of a subtree is terminated as soon as no more rules can be applied to it.
  • If none of the subtrees can be processed further, the processing of the input word is finished.

Simple case study

INPUT WORD
possibility
REGULATE
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
TABLE
Input word [A] [B] [C] Output word rule Level
possibility s / / foos R1 L0
possibility s / / sfoo R1 L0
possibility ssib l t ssibtbarlxorize R2 LO
possibility ss bil t ssibtbarlxorize R2 LO
possibility ss b lit ssibtbarlxorize R2 LO
sfoo fo / / foos R3 L1
sfoo f O / foos R3 L1
ssibtbarlxorize sibtbarlx rize / foos R3 L1
ssibtbarlxorize sibtbarlx rize / foos R3 L1
ssibtbarlxorize sibtbarlx rize / foos R3 L1


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

Application examples

Addition of unary numbers

  • Input word
||||||+||||||||+|+||
  • rule
[A]+[B]→[A][B]
  • Result
|||||||||||||||||

Subtraction of unary numbers

  • Input word
|||||-|||
  • regulate
[A]|-[B]|→[A]-[B]
[A]→[A]
  • Result
||

Multiplication of unary numbers

  • Input word
|||*||||=
  • regulate
|[A]*[B]=[C]→[A]*[B]=[C][B]
*[A]=[B]→[B]
  • Result
||||||||||||

Check parity

  • Input word
101010
  • regulate
[A]00[B]→[A]0[B]
[A]01[B]→[A]1[B]
[A]10[B]→[A]1[B]
[A]11[B]→[A]0[B]
  • Result
1

See also

Web links