Sistema de cadeia reescrito

Predefinição:Sem-fontes Um sistema de cadeia reescrito é um sistema de substituição usado para criar cadeias lógias a partir de determinadas regras de reescrita.

Bases de equivalência para sistemas de cadeias reescritos

Certas formas básicas que formam o sistema de cadeias reescritas são essencialmente equivalentes ao sistema de termos reescritos Supomos que temos cadeias lógicas sobre algum alfabeto A, e apenas damos uma lista de transformações com regras em cadeia lógica sob a forma: $x_0{x}_1\cdots x_n\to y_0{y}_1\cdots y_m,x_i,y_i\in A$; isso indica que qualquer cadeia X ₀x₁...x_n é recolocada com Y ₀y₁...y_m.

Podemos reformular o sistema por um termo de um sistema reescrito—as regras de transformação podem se tornar : $x_0(x_1(\cdots (x_n(x)))\cdots )\to y_0(y_1(\cdots (y_m(x))\cdots ),$ onde cada X x_i e y_i constitui os símbolos de funções em um termo de um sistema reescrito.

Cadeias são esses termos de sistemas reescritos que fazem crescer o termo.

Exemplos

exemplos de modelos computacionais baseados em determinadas cadeias reescritas incluem o algoritmo de Markov, sistemas pós-canônicoss (e.g., sistemas Tags), uma variedade de formas gramaticais, nos L-systems (os últimos se conduzindo a certos tipos de fractais, como o conjunto de Cantor e a Esponja de Menger).

Ver também

• Sistemas de Thue-Semi
• Linguagem de Programação Thue