Semi-Thue system

Semi-Thue system (or also conversion system , word replacement system or string replacement system ) is a rule system for transforming words in theoretical computer science . In contrast to formal grammars, there is only one alphabet with replacement rules , there is no distinction between terminal symbols and non-terminal symbols and there is no start symbol.

Motivated by David Hilbert's lecture in 1900 and the explanations about a logical foundation of mathematics , the Norwegian mathematician Axel Thue initially examined very fundamentally the possibilities that pure derivative calculi open up. From these investigations the current term of the Thue system and the Semi-Thue system developed .

The derivation calculi, which are also frequently used in logic, come from Emil Leon Post (1936) and, as replacement systems for character strings, from Axel Thue as early as 1914. The Thue systems are the starting point for the definition of Chomsky grammars ; they generalize the principle of the replacement of single symbols in character strings to the replacement of whole substrings.

A permissible substitution according to a certain semi-Thue system consists in finding a certain substring in a given string and substituting it with a certain other one. The pair of replacing and replaced substrings is called substitution, the set of all substitutions that are allowed, together with the character alphabet, determines the specific semi-thue system.

Definitions

A Semi-Thue System (STS) is an alphabet along with a set of substitutions, which are usually written as , where u and v are each words over . More formally, a semi-thue system is a pair of an alphabet and a set S of substitutions . It denotes the set of all possible words that can be formed with letters (including the empty word made up of 0 letters). ${\displaystyle \Sigma }$ ${\displaystyle u\rightarrow v}$ ${\displaystyle \Sigma }$ ${\displaystyle (\Sigma ,S)}$ ${\displaystyle \Sigma }$ ${\displaystyle S\subseteq \Sigma ^{*}\times \Sigma ^{*}}$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle \Sigma }$

Often it goes without saying, then you may just name . ${\displaystyle \Sigma }$ ${\displaystyle S}$

The order on certain single-step derivation relation , also formally a subset of is defined as follows: ${\displaystyle \Sigma ^{*}}$ ${\displaystyle \Longrightarrow _{S}}$ ${\displaystyle \Sigma ^{*}\times \Sigma ^{*}}$

• ${\displaystyle w_{1}\Longrightarrow _{S}w_{2}}$, if and only if there are words plus any , so that the decompositions and hold. It must therefore be a prefix of both as , and accordingly suffix for both, and the parts of and in between must form a permissible substitution. ${\displaystyle \alpha ,\beta \in \Sigma ^{*}}$ ${\displaystyle u\rightarrow v\in S}$ ${\displaystyle w_{1}=\alpha u\beta }$ ${\displaystyle w_{2}=\alpha v\beta }$ ${\displaystyle \alpha }$ ${\displaystyle w_{1}}$ ${\displaystyle w_{2}}$ ${\displaystyle \beta }$ ${\displaystyle w_{1}}$ ${\displaystyle w_{2}}$ ${\displaystyle S}$

A derivation according to will generally consist of several individual steps, which are always carried out successively on the result of the previous one. The initial character string and possible results with this procedure are then also in a relationship that is determined by itself. ${\displaystyle S}$ ${\displaystyle \Longrightarrow _{S}}$

The relations correspond to the derivatives in exact steps : ${\displaystyle n\in \mathbb {N} _{0}}$ ${\displaystyle \Longrightarrow _{S}^{n}}$

• ${\displaystyle \Longrightarrow _{S}^{0}\,\,\,\,:=\,\,\,\,id_{\Sigma ^{*}}}$

${\displaystyle id_{\Sigma ^{*}}}$is the identical relation to (with 0 steps, the start and result string are always the same) ${\displaystyle \Sigma ^{*}}$

• ${\displaystyle \Longrightarrow _{S}^{1}\,\,\,\,:=\,\,\,\,\Longrightarrow _{S}}$
• ${\displaystyle \Longrightarrow _{S}^{n}\,\,\,\,:=\,\,\,\,\Longrightarrow _{S}\circ \Longrightarrow _{S}^{n-1}}$ For ${\displaystyle n\in \mathbb {N} ,n>=2}$

(an n-step derivation arises from an (n-1) -step by moving on to a one-step)

The relation corresponds to the derivations in any number of steps

• ${\displaystyle \Longrightarrow _{S}^{*}\,\,\,\,:=\,\,\,\,\{(x,y)|\,\exists _{n\in \mathbb {N} _{0}}\,x\Longrightarrow _{S}^{n}y\}}$, in relation-theoretic language it is precisely the reflexive-transitive shell of . ${\displaystyle \Longrightarrow _{S}}$

The index is often left out if the context is clear. ${\displaystyle S}$ ${\displaystyle S}$

Thue system

When a semi-thue system is symmetrical , i. H. if there is always one too , then it is also called the Thue system . Every rule can also be used in the opposite direction. ${\displaystyle (x,y)\in S}$ ${\displaystyle (y,x)\in S}$

The question of whether a semi-Thue system a word in a word can be rearranged is called the word problem of the system . ${\displaystyle (\Sigma ,S)}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle (\Sigma ,S)}$

Individual evidence

1. ↑ Wolfgang Thomas: "When nobody else dreamed of these things" - Axel Thue and the term replacement. In: Computer Science Spectrum. Volume 33, Number 5, pp. 504-508, doi : 10.1007 / s00287-010-0468-9 .