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:

    “It is very hard to give a just definition of love. The most we can say of it is this: that in the soul, it is a desire to rule; in the spirit, it is a sympathy; and in the body, it is but a hidden and subtle desire to possess—after many mysteries—what one loves.”
    —François, Duc De La Rochefoucauld (1613–1680)

    “According to our social pyramid, all men who feel displaced racially, culturally, and/or because of economic hardships will turn on those whom they feel they can order and humiliate, usually women, children, and animals—just as they have been ordered and humiliated by those privileged few who are in power. However, this definition does not explain why there are privileged men who behave this way toward women.”
    —Ana Castillo (b. 1953)

    “The man who knows governments most completely is he who troubles himself least about a definition which shall give their essence. Enjoying an intimate acquaintance with all their particularities in turn, he would naturally regard an abstract conception in which these were unified as a thing more misleading than enlightening.”
    —William James (1842–1910)