Semi-Thue system (original) (raw)
System półthueowski to zbliżony do gramatyk typu 0. Jedyna różnica polega na tym, że w systemach półthueowskich nie ma podziału na symbole terminalne i nieterminalne ani wyróżnionego symbolu początkowego. Formalnie, system półthueowski S nad alfabetem A jest relacją gdzie oznacza zbiór wszystkich słów nad alfabetem A (domknięcie Kleenego). System półthueowski, w którym wszystkie reguły są odwracalne (tj. jeśli jest regułą, to też), nazywany jest systemem Thuego.
| Property | Value |
|---|---|
| dbo:abstract | Semi-Thue-System (oder auch Umformungssystem, Wortersetzungssystem oder Stringersetzungssystem) ist in der Theoretischen Informatik ein Regelsystem zur Transformation von Wörtern. Anders als bei formalen Grammatiken liegt aber nur ein Alphabet mit Ersetzungsregeln vor, es wird nicht zwischen Terminalsymbolen und Nichtterminalsymbolen unterschieden und es gibt kein Startsymbol. Motiviert durch David Hilberts Vortrag im Jahre 1900 und die Ausführungen über eine logische Fundamentierung der Mathematik untersuchte der norwegische Mathematiker Axel Thue die Möglichkeiten, die reine Ableitungskalküle eröffnen, zunächst ganz grundlegend. Aus diesen Untersuchungen hat sich der heutige Begriff des Thue-Systems und des Semi-Thue-Systems herausgebildet. Die auch in der Logik häufig verwendeten Ableitungs-Kalküle stammen von Emil Leon Post (1936) und als Ersetzungssysteme für Zeichenketten schließlich schon 1914 von Axel Thue. Die Thue-Systeme bilden den Ausgangspunkt zur Definition von Chomsky-Grammatiken; sie verallgemeinern das Prinzip der Ersetzung von Einzelsymbolen in Zeichenketten auf die Ersetzung ganzer Teilzeichenketten. Eine zulässige Ersetzung nach einem bestimmten Semi-Thue-System besteht darin, in einer vorliegenden Zeichenkette eine bestimmte Teilzeichenkette vorzufinden und diese durch eine bestimmte andere zu substituieren. Das Paar aus ersetzender und ersetzter Teilzeichenkette nennt man Substitution, die Menge aller Substitutionen, die man zulässt, bestimmt zusammen mit dem Zeichenalphabet das spezifische Semi-Thue-System. (de) In theoretical computer science and mathematical logic a string rewriting system (SRS), historically called a semi-Thue system, is a rewriting system over strings from a (usually finite) alphabet. Given a binary relation between fixed strings over the alphabet, called rewrite rules, denoted by , an SRS extends the rewriting relation to all strings in which the left- and right-hand side of the rules appear as substrings, that is , where , , , and are strings. The notion of a semi-Thue system essentially coincides with the presentation of a monoid. Thus they constitute a natural framework for solving the word problem for monoids and groups. An SRS can be defined directly as an abstract rewriting system. It can also be seen as a restricted kind of a term rewriting system. As a formalism, string rewriting systems are Turing complete. The semi-Thue name comes from the Norwegian mathematician Axel Thue, who introduced systematic treatment of string rewriting systems in a 1914 paper. Thue introduced this notion hoping to solve the word problem for finitely presented semigroups. Only in 1947 was the problem shown to be undecidable— this result was obtained independently by Emil Post and A. A. Markov Jr. (en) En informatique théorique et en logique mathématique, un système de semi-Thue ou sa version symétrique, un système de Thue, est un système de réécriture de chaînes de caractères ou mots, appelé ainsi d'après son inventeur, le mathématicien norvégien Axel Thue. Contrairement aux grammaires formelles, un tel système ne distingue pas entre symboles terminaux et non terminaux, et ne possède pas d'axiome. Un système de semi-Thue est donné par une relation binaire finie fixe entre mots sur un alphabet donné, dont les éléments sont appelés les règles de réécriture, et notées . La relation est étendue en une relation de réécriture entre tous les mots dans lesquels les parties gauche et droite d'une règle apparaissent en facteur, en d'autres termes on a la relation , pour une règle de et des mots , et quelconques. Les systèmes de semi-Thue sont Turing-complets. Ils sont voisins des systèmes de Post. Axel Thue a étudié les systèmes de réécriture dans deux articles, l'un sur la réécriture de termes, l'autre sur la réécriture des mots ; c'est du deuxième que dérivent les systèmes de semi-Thue. Le problème de décider de l'existence d'une relation entre deux mots est indécidable. (fr) System półthueowski to zbliżony do gramatyk typu 0. Jedyna różnica polega na tym, że w systemach półthueowskich nie ma podziału na symbole terminalne i nieterminalne ani wyróżnionego symbolu początkowego. Formalnie, system półthueowski S nad alfabetem A jest relacją gdzie oznacza zbiór wszystkich słów nad alfabetem A (domknięcie Kleenego). System półthueowski, w którym wszystkie reguły są odwracalne (tj. jeśli jest regułą, to też), nazywany jest systemem Thuego. (pl) Na ciência da computação e na matemática, um sistema de Thue-Semi é um sistema de cadeia reescrito. Recebeu o nome devido aos trabalhos do matemático norueguês Axel Thue, que iniciou tratamentos sistemáticos à sistemas de cadeia reescritos nos princípios do século XX. (pt) |
| dbo:wikiPageExternalLink | https://projecteuclid.org/euclid.jsl/1183395203 |
| dbo:wikiPageID | 2452154 (xsd:integer) |
| dbo:wikiPageInterLanguageLink | dbpedia-ja:文字列書き換え系 |
| dbo:wikiPageLength | 21121 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1109402028 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Preorder dbr:Ronald_V._Book dbr:Elaine_Rich dbr:Monoidal_category dbr:Andrey_Markov_(Soviet_mathematician) dbr:Binary_relation dbr:Presentation_of_a_monoid dbr:Mathematical_logic dbr:Rewriting dbr:Empty_string dbr:Congruence_relation dbr:Reflexive_transitive_closure dbr:Reflexive_transitive_symmetric_closure dbr:Alphabet_(computer_science) dbr:Logic dbr:String_concatenation dbr:Propositional_logic dbr:String_(computer_science) dbr:Theoretical_computer_science dbr:Turing_complete dbr:Axel_Thue dbr:BQP dbr:Tuple dbr:Post_canonical_system dbr:Unrestricted_grammar dbr:Alonzo_Church dbr:Equivalence_relation dbr:Finite_set dbr:Formal_languages dbr:Noam_Chomsky dbr:Formal_grammar dbr:Formal_language dbr:Quantum_Turing_machine dbr:Halting_problem dbr:Isomorphic dbr:Term_rewriting dbr:Terminal_symbol dbr:Abstract_rewriting_system dbc:Formal_languages dbc:Rewriting_systems dbc:Theory_of_computation dbr:Chomsky_hierarchy dbr:L-system dbr:Binary_operation dbr:Symmetric_relation dbr:Martin_Davis_(mathematician) dbr:Free_group dbr:Free_monoid dbr:Factor_monoid dbr:Term-rewriting dbr:Word_problem_(mathematics) dbr:Kleene_star dbr:MU_puzzle dbr:Turing_machine dbr:Undecidable_problem dbr:Substring dbr:The_Journal_of_Symbolic_Logic dbr:Turing_machines dbr:Bicyclic_monoid dbr:Emil_Post dbr:Theorem_proving dbr:A._A._Markov dbr:Monadic_(arity) dbr:Monoid_presentation |
| dbp:wikiPageUsesTemplate | dbt:Cite_journal dbt:Dubious dbt:Math dbt:Mvar dbt:Reflist dbt:Short_description dbt:Isbn dbt:Formal_languages_and_grammars |
| dct:subject | dbc:Formal_languages dbc:Rewriting_systems dbc:Theory_of_computation |
| rdf:type | yago:Artifact100021939 yago:Instrumentality103575240 yago:Object100002684 yago:PhysicalEntity100001930 yago:System104377057 yago:Whole100003553 yago:WikicatRewritingSystems |
| rdfs:comment | System półthueowski to zbliżony do gramatyk typu 0. Jedyna różnica polega na tym, że w systemach półthueowskich nie ma podziału na symbole terminalne i nieterminalne ani wyróżnionego symbolu początkowego. Formalnie, system półthueowski S nad alfabetem A jest relacją gdzie oznacza zbiór wszystkich słów nad alfabetem A (domknięcie Kleenego). System półthueowski, w którym wszystkie reguły są odwracalne (tj. jeśli jest regułą, to też), nazywany jest systemem Thuego. (pl) Na ciência da computação e na matemática, um sistema de Thue-Semi é um sistema de cadeia reescrito. Recebeu o nome devido aos trabalhos do matemático norueguês Axel Thue, que iniciou tratamentos sistemáticos à sistemas de cadeia reescritos nos princípios do século XX. (pt) Semi-Thue-System (oder auch Umformungssystem, Wortersetzungssystem oder Stringersetzungssystem) ist in der Theoretischen Informatik ein Regelsystem zur Transformation von Wörtern. Anders als bei formalen Grammatiken liegt aber nur ein Alphabet mit Ersetzungsregeln vor, es wird nicht zwischen Terminalsymbolen und Nichtterminalsymbolen unterschieden und es gibt kein Startsymbol. (de) En informatique théorique et en logique mathématique, un système de semi-Thue ou sa version symétrique, un système de Thue, est un système de réécriture de chaînes de caractères ou mots, appelé ainsi d'après son inventeur, le mathématicien norvégien Axel Thue. Contrairement aux grammaires formelles, un tel système ne distingue pas entre symboles terminaux et non terminaux, et ne possède pas d'axiome. Le problème de décider de l'existence d'une relation entre deux mots est indécidable. (fr) In theoretical computer science and mathematical logic a string rewriting system (SRS), historically called a semi-Thue system, is a rewriting system over strings from a (usually finite) alphabet. Given a binary relation between fixed strings over the alphabet, called rewrite rules, denoted by , an SRS extends the rewriting relation to all strings in which the left- and right-hand side of the rules appear as substrings, that is , where , , , and are strings. (en) |
| rdfs:label | Semi-Thue-System (de) Système de Thue (fr) System półthueowski (pl) Semi-Thue system (en) Sistemas de Thue-Semi (pt) |
| owl:sameAs | freebase:Semi-Thue system yago-res:Semi-Thue system wikidata:Semi-Thue system dbpedia-de:Semi-Thue system dbpedia-fr:Semi-Thue system dbpedia-hr:Semi-Thue system dbpedia-pl:Semi-Thue system dbpedia-pt:Semi-Thue system https://global.dbpedia.org/id/P2S5 |
| prov:wasDerivedFrom | wikipedia-en:Semi-Thue_system?oldid=1109402028&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Semi-Thue_system |
| is dbo:wikiPageRedirects of | dbr:Semi-Thue dbr:String_rewriting_system dbr:Semi-Thue_problem dbr:Word_problem_for_semigroups dbr:Thue_system dbr:Semi-Thue_grammar dbr:String_rewriting |
| is dbo:wikiPageWikiLink of | dbr:Monoidal_category dbr:Index_of_philosophy_articles_(R–Z) dbr:Context-free_grammar dbr:Andrey_Markov_Jr. dbr:Prefix_grammar dbr:Axel_Thue dbr:Backus–Naur_form dbr:Unrestricted_grammar dbr:Formal_grammar dbr:Semi-Thue dbr:String_rewriting_system dbr:Semi-Thue_problem dbr:Word_problem_for_semigroups dbr:Thue_system dbr:Semi-Thue_grammar dbr:String_rewriting |
| is foaf:primaryTopic of | wikipedia-en:Semi-Thue_system |