Sistemas de Thue-Semi

Na ciência da computação e na matemática, um sistema de Thue-Semi é um sistema de cadeia reescrito. Recebeu o nome devido aos trabalhos do matemático norueguês Axel Thue, que iniciou tratamentos sistemáticos à sistemas de cadeia reescritos nos princípios do século XX.

Definição

Sendo $\Sigma$ um alfabeto finito, e $\Sigma^*$ a trava de Kleene sobre $\Sigma$. Então um sistema de Thue-Semi é um invólucro $T:=(\Sigma, R)$ com

$R \subseteq \Sigma^* \times \Sigma^*.$

Os elementos de R são chamados de produções ou regras reescritas, e são habitualmente escritos como regras de $u \rightarrow v$. Note que R pode ser infinito; mas caso um sistema de thue-semi seja simétrico (i.e. $R^{-1}=R$), ele será chamado de sistema de Thue.

Ver também

• Linguagem de Programação Thue