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 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 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. 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.
Read more about Semi-Thue System: Definition, Thue Congruence, Factor Monoid and Monoid Presentations, The Word Problem For Semi-Thue Systems, Connections With Other Notions, History and Importance, See Also
Famous quotes containing the word system:
“The violent illiteracies of the graffiti, the clenched silence of the adolescent, the nonsense cries from the stage-happening, are resolutely strategic. The insurgent and the freak-out have broken off discourse with a cultural system which they despise as a cruel, antiquated fraud. They will not bandy words with it. Accept, even momentarily, the conventions of literate linguistic exchange, and you are caught in the net of the old values, of the grammars that can condescend or enslave.”
—George Steiner (b. 1929)