Semi-Thue-System

Semi-Thue system (or conversion system, word substitution system or string rewriting system ) is in theoretical computer science, a control system for the transformation of words. In contrast to formal grammars but there is only one alphabet with replacement rules, there is no distinction between terminal symbols and nonterminal symbols and there is no start symbol.

Motivated by David Hilbert's lecture in 1900 and the section on logical foundations of mathematics, the Norwegian mathematician Axel Thue examined the possibilities that pure derivation calculi, initially quite fundamentally. From these studies, the present-day concept of the Thue system and the semi-Thue system has emerged.

The derivation calculi frequently used also in the logic come from Emil Leon Post (1936) and as replacement systems for strings finally in 1914 by Axel Thue. The Thue systems form the starting point for the definition of Chomsky grammars; They generalize the principle of substitution of individual symbols in strings on the replacement of entire substrings.

An acceptable replacement for a specific semi-Thue system is to be found a certain substring in an existing string and to replace by a certain other. The pair of substitution and the replaced substring is called substitution, the set of all substitutions that you allow determining with the character alphabet, the specific semi-Thue system.

Definitions

A semi-Thue system (STS) is an alphabet together with a quantity of substitution, which are commonly referred to as writing, where u and v are each about words. Formal a semi-Thue system is thus a pair of alphabet and a set S of substitutions.

Often goes alone, then you can call even if only.

The thus defined to specific single-step derivation relation formally also a subset of is:

• , If and only if there are words and to some, so that the decompositions and apply. So there must be a prefix of both how to be in accordance with both the suffix and the parts of and in between just have to make a substitution after allowable.

A derivation is i.a. according to composed of several steps, which are always performed successively on the result of each previous one. Initial character string and possible with this procedure results are then also in a direction determined by relation alone.

The derivations in the exact steps correspond to the relations:

The derivations in any number of steps corresponds to the relation

• , It is in relation theoretical way of speaking just the reflexive - transitive closure of.

The index is often omitted when the context is clear.

Thue system

If a semi-Thue system is symmetric, that is, if with always is, then it is called also Thue system. Each rule is applicable here also in the opposite direction.

The question of whether one word can be transformed into a word with a semi-Thue system is called the word problem of the system.