Semi-Thue system
Semi-Thue system is a rewriting system over strings from an alphabet.
All 2 facts, and where they come from
Facts
2 facts · 0 confirmed by two sources · 0 cited · 2 from one source
Where this comes from
Papalocal keeps its own record. It started from these sources; what each one said is kept here as it was copied, so a change on their side never changes this page by itself. Tap one to read its version.
What Wikidata says · copied November 17, 2026 · revision 2514182530
- Described as
- rewriting system over strings from an alphabet
- Other names
- string rewriting system, SRS
- What it is
- mathematical concept
- Named after
- Axel Thue
- Wikipedias with a page
- 6
Wikidata item Q1378504 (wikidata.org/wiki/Q1378504), public domain (CC0). Copied 2026-11-17.
What Wikipedia says · copied November 17, 2026 · revision 1378037170
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 R between fixed strings over the alphabet, called rewrite rules, denoted by s→t, 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 usv→utv, where s, t, u, and v 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, in which all function symbols have an arity of at most 1. 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.
From the Wikipedia article “Semi-Thue system” (en.wikipedia.org/wiki/Semi-Thue_system), by its contributors, under CC BY-SA 4.0 (creativecommons.org/licenses/by-sa/4.0/). Copied 2026-11-17; not changed.
Confirmed Two sources agree. Cited One source, and it names where it got it. One source One source, without a reference of its own. Sources disagree The sources disagree. We show the best-supported value and keep theirs below.
