Post canonical system

Post canonical system

A Post canonical system, as created by Emil Post, is a string-manipulation system that starts with finitely-many strings and repeatedly transforms them by applying a finite set of specified rules of a certain form, thus generating a formal language.

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:

:egin{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

: g_0 $_1 g_1 $_2 g_2 dots $_m g_m ightarrow h_0 $'_1 h_1 $'_2 h_2 dots $'_n h_n

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.

Example (well-formed bracket expressions)

Alphabet: { [, ] } Initial word: [] Production rules: (1) "$" → ["$"] (2) "$" → "$$" (3) "$"1 [] "$"2 → "$"1"$"2 Derivation of a few words in the language of well-formed bracket expressions: [] initial word [] [] by (2) [] [] by (1) [] [] [] [] by (2) [] [] by (3) [] [] [] by (3) ...

Normal-form theorem

A Post canonical system is said to be in "normal form" if it has only one initial word and every production rule is of the simple form

: gP ightarrow Ph

Post 1943 proved the remarkable Normal-form Theorem, which applies to the most-general type of Post canonical system: :Given any Post canonical system on an alphabet A, a Post canonical system in "normal form" can be constructed from it, possibly enlarging the alphabet, such that the set of words involving only letters of A that are generated by the normal-form system is exactly the set of words generated by the original system.

Tag systems, which comprise a universal computational model, are notable examples of Post normal-form system, being also "monogenic". (A canonical system is said to be "monogenic" if, given any string, at most one new string can be produced from it in one step — i.e., the system is deterministic.)

tring rewriting systems, Type-0 formal grammars

A string rewriting system is a special type of Post canonical system with a single initial word, and the productions are each of the form

: P_1 g P_2 ightarrow P_1 h P_2

That is, each production rule is a simple substitution rule, often written in the form "g" → "h". It has been proved that any Post canonical system is reducible to such a "substitution system", which, as a formal grammar, is also called a "phrase-structure grammar", or a "type-0 grammar" in the Chomsky hierarchy.

References

* Emil Post, "Formal Reductions of the General Combinatorial Decision Problem," "American Journal of Mathematics" 65 (2): 197-215, 1943.
* Marvin Minsky, "Computation: Finite and Infinite Machines", Prentice-Hall, Inc., N.J., 1967.


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Canonical books — Book Book (b[oo^]k), n. [OE. book, bok, AS. b[=o]c; akin to Goth. b[=o]ka a letter, in pl. book, writing, Icel. b[=o]k, Sw. bok, Dan. bog, OS. b[=o]k, D. boek, OHG. puoh, G. buch; and fr. AS. b[=o]c, b[=e]ce, beech; because the ancient Saxons and …   The Collaborative International Dictionary of English

  • Tag system — A tag system is a deterministic computational model published by Emil Leon Post in 1943 as a simple form of Post canonical system. A tag system may also be viewed as an abstract machine, called a Post tag machine (not to be confused with Post… …   Wikipedia

  • Semi-Thue system — In computer science and mathematics a Semi Thue system (also called a string rewriting system [Book and Otto, p. 36] ) is a type of term rewriting system. It is named after the Norwegian mathematician Axel Thue, who introduced systematic… …   Wikipedia

  • Emil Leon Post — Infobox Scientist name = Emil Leon Post image width = birth date = February 11, 1897 birth place = Augustów, then Russian Empire death date = April 21 1954, death place = New York City, flagicon|USA U.S. residence = nationality = field =… …   Wikipedia

  • Book post — Book Book (b[oo^]k), n. [OE. book, bok, AS. b[=o]c; akin to Goth. b[=o]ka a letter, in pl. book, writing, Icel. b[=o]k, Sw. bok, Dan. bog, OS. b[=o]k, D. boek, OHG. puoh, G. buch; and fr. AS. b[=o]c, b[=e]ce, beech; because the ancient Saxons and …   The Collaborative International Dictionary of English

  • Non-canonical works related and derived from Sherlock Holmes — Sherlock Holmes has long been a popular character for authors and creatives other than Arthur Conan Doyle. Their works can be grouped into four broad categories: new Sherlock Holmes stories; stories in which Holmes appears in a cameo role;… …   Wikipedia

  • Non-canonical Sherlock Holmes works — Sherlock Holmes has long been a popular character for authors and creators other than Arthur Conan Doyle. Their works can be grouped into four broad categories: new Sherlock Holmes stories; stories in which Holmes appears in a cameo role; stories …   Wikipedia

  • Formal grammar — In formal semantics, computer science and linguistics, a formal grammar (also called formation rules) is a precise description of a formal language ndash; that is, of a set of strings over some alphabet. In other words, a grammar describes which… …   Wikipedia

  • MU puzzle — The MU puzzle is a puzzle stated by Douglas Hofstadter and is found in Gödel, Escher, Bach . As stated, it is an example of a Post canonical system and can be reformulated as a term rewriting system. The puzzle Let s suppose to have the symbols M …   Wikipedia

  • BIBLE — THE CANON, TEXT, AND EDITIONS canon general titles the canon the significance of the canon the process of canonization contents and titles of the books the tripartite canon …   Encyclopedia of Judaism

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”