Sistemas de Thue-Semi

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Esta página ou secção não cita nenhuma fonte ou referência, o que compromete sua credibilidade (desde janeiro de 2010).
Por favor, melhore este artigo providenciando fontes fiáveis e independentes, inserindo-as no corpo do texto por meio de notas de rodapé. Encontre fontes: Googlenotícias, livros, acadêmicoScirusBing. Veja como referenciar e citar as fontes.

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[editar | editar código-fonte]

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[editar | editar código-fonte]

Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.