17/09/2010
Condições finitas em apresentações de monóides
O monóide livre sobre um determinado alfabeto, no qual
consideramos um conjunto de regras de reescrita das suas palavras,
pode ser interpretado como um Sistema de Reescrita (SR). Por sua vez
esta noção de SR coincide, na sua essência, com a noção de
apresentação de um monóide. Como se sabe, pelo Teorema de Post-Markov,
o problema da palavra, isto é, a decisão sobre se duas palavras de um
mesmo sistema de reescrita representam o mesmo elemento do monóide,
não é decidível no caso mais genérico [1,2]. No entanto, para certos
casos de SR, nomeadamente os finitos e completos, o problema da
palavra torna-se decidível.
Ora a propriedade de decidibilidade é invariante segundo qualquer
apresentação finita de um mesmo monóide. O mesmo não acontece para a
propriedade de ser completa. Em 1994, Squier [3] introduziu uma nova
propriedade - tipo de derivação finita (FDT) - que é verificada por
qualquer monóide definido por um sistema de reescrita finito e
completo e é também invariante segundo qualquer apresentação finita
desse monóide.
Nesta comunicação abordaremos com mais detalhe os conceitos e
resultados anteriormente mencionados.
[1] A. A. Markov, On the impossibility of certain algorithms in the
theory of associative systems, I.C.R. (Dokl.) Acad. Sci. URSS 55
(1947), 583-586 (em inglês).
[2] E. L. Post, Recursive unsolvability of a problem of Thue, J.
Symbolic Logic, 12 (1947), 1-11.
[3] Craig C. Squier, Friedrich Otto, Yuji Kobayashi, A Finiteness
Condition for Rewriting Systems. Theor. Comput. Sci. 131(2): 271-294
(1994) |
|
