A Post canonical system, also known as a Post production 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 j of specified rules of a certain form, thus generating a formal language. Today they are mainly of historical relevance because every Post canonical system can be reduced to a string rewriting system (semi-Thue system), which is a simpler formulation. Both formalisms are Turing complete.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Système de Post (fr)
- Post canonical system (en)
- Sistema canônico de Post (pt)
- Числення Поста (uk)
|
| rdfs:comment
| - A Post canonical system, also known as a Post production 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 j of specified rules of a certain form, thus generating a formal language. Today they are mainly of historical relevance because every Post canonical system can be reduced to a string rewriting system (semi-Thue system), which is a simpler formulation. Both formalisms are Turing complete. (en)
- En informatique théorique et en logique mathématique, un système de Post, ou système canonique de Post, appelé ainsi d’après son créateur Emil Post, est un système de manipulation de chaînes de caractères qui commence avec un nombre fini de mots et les transforme par application d’un ensemble fini de règles d’un forme particulière, et par là engendre un langage formel. Ces système ont surtout un intérêt historique car tout système de Post peut être réduit à un système de réécriture de mots (un système de semi-Thue) qui est une formulation plus simple. Les deux formalismes -- système de Post et réécriture -- sont Turing-complets. (fr)
- Числення Поста — клас числень, який запропонував американський математик Еміль Пост. Числення Поста можна розглядати як математичне уточнення інтуїтивного поняття алгоритму. (uk)
- Um sistema canônico de Post é uma tripla (A,I,R), onde
* A é um alfabeto finito, e finitas (possivelmente vazias) cadeias em A são chamadas palavras.
* I é um conjunto finito de palavras iniciais.
* R é um conjunto finito de regras de transformação de cadeias (chamadas regras de produção), cada regra sendo da seguinte forma: Em vários contextos, cada regra de produção tem apenas um antecedente, tomando a forma mais simples (pt)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - A Post canonical system, also known as a Post production 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 j of specified rules of a certain form, thus generating a formal language. Today they are mainly of historical relevance because every Post canonical system can be reduced to a string rewriting system (semi-Thue system), which is a simpler formulation. Both formalisms are Turing complete. (en)
- En informatique théorique et en logique mathématique, un système de Post, ou système canonique de Post, appelé ainsi d’après son créateur Emil Post, est un système de manipulation de chaînes de caractères qui commence avec un nombre fini de mots et les transforme par application d’un ensemble fini de règles d’un forme particulière, et par là engendre un langage formel. Ces système ont surtout un intérêt historique car tout système de Post peut être réduit à un système de réécriture de mots (un système de semi-Thue) qui est une formulation plus simple. Les deux formalismes -- système de Post et réécriture -- sont Turing-complets. (fr)
- Um sistema canônico de Post é uma tripla (A,I,R), onde
* A é um alfabeto finito, e finitas (possivelmente vazias) cadeias em A são chamadas palavras.
* I é um conjunto finito de palavras iniciais.
* R é um conjunto finito de regras de transformação de cadeias (chamadas regras de produção), cada regra sendo da seguinte forma: onde cada g e h é uma palavra fixa específica, e cada $ e $' é uma variável servindo como uma palavra arbitrária. As cadeias antes e depois da seta em uma regra de produção são chamadas os antecedentes e consequentes da regra, respectivamente. É preciso que cada $' nos consequentes seja um dos $s nos antecedentes desta regra, e cada antecedente e consequente conterem ao menos uma variável. Em vários contextos, cada regra de produção tem apenas um antecedente, tomando a forma mais simples A linguagem formal gerada por um sistema canônico de Post é o conjunto cujos elementos são as palavras iniciais juntas com todas as palavras obteníveis a partir delas através da aplicação repetida das regras de produção. Tais conjuntos são recursivamente enumeráveis e toda linguagem recursivamente enumerável é a restrição de algum conjunto deste tipo para um sub-alfabeto de A. (pt)
- Числення Поста — клас числень, який запропонував американський математик Еміль Пост. Числення Поста можна розглядати як математичне уточнення інтуїтивного поняття алгоритму. (uk)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)