Post Canonical System - Definition

Definition

A Post canonical system is a triplet (A,I,R), where

  • A is a finite alphabet, and finite (possibly empty) strings on A are called words.
  • I is a finite set of initial words.
  • R is a finite set of string-transforming rules (called production rules), each rule being of the following form:


\begin{matrix} g_{10}\ $_{11}\ g_{11}\ $_{12}\ g_{12} \ \dots \ $_{1m_1}\ g_{1m_1} \\ g_{20}\ $_{21}\ g_{21}\ $_{22}\ g_{22} \ \dots \ $_{2m_2}\ g_{2m_2} \\ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \\ g_{k0}\ $_{k1}\ g_{k1}\ $_{k2}\ g_{k2} \ \dots \ $_{km_k}\ g_{km_k} \\ \\ \downarrow \\ \\ h_0 \ $'_1 \ h_1 \ $'_2 \ h_2 \ \dots \ $'_n \ h_n \\ \end{matrix}


where each g and h is a specified fixed word, and each $ and $' is a variable standing for an arbitrary word. The strings before and after the arrow in a production rule are called the rule's antecedents and consequent, respectively. It is required that each $' in the consequent be one of the $s in the antecedents of that rule, and that each antecedent and consequent contain at least one variable.

In many contexts, each production rule has only one antecedent, thus taking the simpler form

The formal language generated by a Post canonical system is the set whose elements are the initial words together with all words obtainable from them by repeated application of the production rules. Such sets are precisely the recursively enumerable languages.


Read more about this topic:  Post Canonical System

Famous quotes containing the word definition:

    “Was man made stupid to see his own stupidity?
    Is God by definition indifferent, beyond us all?
    Is the eternal truth man’s fighting soul
    Wherein the Beast ravens in its own avidity?”
    —Richard Eberhart (b. 1904)

    “Although there is no universal agreement as to a definition of life, its biological manifestations are generally considered to be organization, metabolism, growth, irritability, adaptation, and reproduction.”
    —The Columbia Encyclopedia, Fifth Edition, the first sentence of the article on “life” (based on wording in the First Edition, 1935)

    “Perhaps the best definition of progress would be the continuing efforts of men and women to narrow the gap between the convenience of the powers that be and the unwritten charter.”
    —Nadine Gordimer (b. 1923)