Post canonical system (original) (raw)
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.
| Property | Value |
|---|---|
| dbo: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 ′eˊumavariaˊvelservindocomoumapalavraarbitraˊria.Ascadeiasantesedepoisdasetaemumaregradeproduc\ca |
| dbo:wikiPageID | 13995373 (xsd:integer) |
| dbo:wikiPageLength | 5018 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1029956360 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:American_Journal_of_Mathematics dbr:Tag_system dbr:Turing_complete dbr:Formal_grammar dbr:Formal_language dbr:Production_(computer_science) dbr:Recursively_enumerable dbc:Formal_languages dbc:Models_of_computation dbr:Chomsky_hierarchy dbr:Marvin_Minsky dbr:String_rewriting_system dbr:Emil_Post dbr:][ |
| dbp:wikiPageUsesTemplate | dbt:Mvar dbt:No_footnotes |
| dct:subject | dbc:Formal_languages dbc:Models_of_computation |
| gold:hypernym | dbr:System |
| rdf:type | yago:WikicatModelsOfComputation yago:Assistant109815790 yago:CausalAgent100007347 yago:LivingThing100004258 yago:Model110324560 yago:Object100002684 yago:Organism100004475 yago:Person100007846 yago:PhysicalEntity100001930 yago:Worker109632518 yago:YagoLegalActor yago:YagoLegalActorGeo yago:Whole100003553 |
| 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) |
| rdfs:label | Système de Post (fr) Post canonical system (en) Sistema canônico de Post (pt) Числення Поста (uk) |
| owl:sameAs | freebase:Post canonical system yago-res:Post canonical system wikidata:Post canonical system dbpedia-fr:Post canonical system dbpedia-pt:Post canonical system dbpedia-uk:Post canonical system https://global.dbpedia.org/id/4u8GA |
| prov:wasDerivedFrom | wikipedia-en:Post_canonical_system?oldid=1029956360&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Post_canonical_system |
| is dbo:wikiPageWikiLink of | dbr:History_of_compiler_construction dbr:Computability dbr:Emil_Leon_Post dbr:Tag_system dbr:Phrase_structure_grammar dbr:Formal_grammar dbr:Formal_language dbr:Production_(computer_science) dbr:MU_puzzle dbr:Semi-Thue_system |
| is foaf:primaryTopic of | wikipedia-en:Post_canonical_system |