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.

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. 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 indecidível & mdash; este resultado foi obtido independentemente por Emil Post e A. A. Markov Jr..

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, 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

• Linguagem de Programação Thue