Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Semi-Thue_system> ?p ?o. }
Showing items 1 to 28 of
28
with 100 items per page.
- Semi-Thue_system abstract "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 in 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. It wasn't until 1947 the problem was shown to be undecidable— this result was obtained independently by Emil Post and A. A. Markov Jr.".
- Semi-Thue_system wikiPageID "2452154".
- Semi-Thue_system wikiPageRevisionID "596474067".
- Semi-Thue_system hasPhotoCollection Semi-Thue_system.
- Semi-Thue_system subject Category:Formal_languages.
- Semi-Thue_system subject Category:Rewriting_systems.
- Semi-Thue_system subject Category:Theory_of_computation.
- Semi-Thue_system type Artifact100021939.
- Semi-Thue_system type Instrumentality103575240.
- Semi-Thue_system type Object100002684.
- Semi-Thue_system type PhysicalEntity100001930.
- Semi-Thue_system type RewritingSystems.
- Semi-Thue_system type System104377057.
- Semi-Thue_system type Whole100003553.
- Semi-Thue_system comment "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.".
- Semi-Thue_system label "Semi-Thue system".
- Semi-Thue_system label "Semi-Thue-System".
- Semi-Thue_system label "Sistemas de Thue-Semi".
- Semi-Thue_system label "System półthueowski".
- Semi-Thue_system sameAs Semi-Thue-System.
- Semi-Thue_system sameAs System_półthueowski.
- Semi-Thue_system sameAs Sistemas_de_Thue-Semi.
- Semi-Thue_system sameAs m.07f283.
- Semi-Thue_system sameAs Q1378504.
- Semi-Thue_system sameAs Q1378504.
- Semi-Thue_system sameAs Semi-Thue_system.
- Semi-Thue_system wasDerivedFrom Semi-Thue_system?oldid=596474067.
- Semi-Thue_system isPrimaryTopicOf Semi-Thue_system.