Mostrar código-fonte de Sistemas de Thue-Semi

{{mais-fontes|data=janeiro de 2010}}
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 [[Noruega|norueguês]] [[Axel Thue]], que iniciou tratamentos sistemáticos à sistemas de cadeia reescritos nos princípios do [[século XX]].

== Definição ==
Sendo <math>\Sigma</math> um [[alfabeto]] finito, e <math>\Sigma^*</math> a ''trava de Kleene'' sobre <math>\Sigma</math>. Então um sistema de Thue-Semi é um invólucro <math>T:=(\Sigma, R)</math> com
:<math>R \subseteq \Sigma^* \times \Sigma^*.</math>

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

Um SRS pode ser definido diretamente como um [[sistema de reescrita abstrata]]. Também pode ser visto como um tipo restrito de um sistema [[reescrevendo termos]]. Como formalismo, os sistemas de reescrita de strings são [[Turing complete]]. O nome semi-Thue vem do matemático norueguês [[Axel Thue]], que introduziu o tratamento sistemático dos sistemas de reescrita de cordas em um artigo de 1914.<ref>Book and Otto, p. 36</ref> Thue introduziu essa noção na esperança de resolver o problema da palavra para semigrupos finitamente apresentados. Somente em 1947 o problema mostrou ser [[problema indecidível | indecidível]] & mdash; este resultado foi obtido independentemente por [[Emil Post]] e [[Andrey Markov (matemático soviético)|A. A. Markov Jr.]].<ref>Abramsky et al. p. 416</ref><ref>Salomaa et al., p.444</ref>

{{Referências}}

== Bibliografia ==
* [[Ronald V. Book]] and Friedrich Otto, ''String-rewriting Systems'', Springer, 1993, {{isbn|0-387-97965-4}}.
* Matthias Jantzen, ''Confluent string rewriting'', Birkhäuser, 1988, {{isbn|0-387-13715-7}}.
* [[Martin Davis (mathematician)|Martin Davis]], Ron Sigal, Elaine J. Weyuker, ''Computability, complexity, and languages: fundamentals of theoretical computer science'', 2nd ed., Academic Press, 1994, {{isbn|0-12-206382-1}}, chapter 7
* Elaine Rich, ''Automata, computability and complexity: theory and applications'', Prentice Hall, 2007, {{isbn|0-13-228806-0}}, chapter 23.5.
* Samson Abramsky, Dov M. Gabbay, Thomas S. E. Maibaum (ed.), ''Handbook of Logic in Computer Science: Semantic modelling'', Oxford University Press, 1995, {{isbn|0-19-853780-8}}.
* Grzegorz Rozenberg, Arto Salomaa (ed.), ''Handbook of Formal Languages: Word, language, grammar'', Springer, 1997, {{isbn|3-540-60420-0}}.

==Ver também==
*[[Thue|Linguagem de Programação Thue]] 

{{Esboço-matemática}}


{{DEFAULTSORT:Sistemas Thue Semi}}
[[Categoria:Teoria da computação]]
[[Categoria:Linguagens formais]]