Sistemas de Thue-Semi

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Este artigo não cita fontes fiáveis e independentes. (desde janeiro de 2010). Por favor, adicione referências e insira-as corretamente no texto ou no rodapé. Conteúdo sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)

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.