Subconjuntos racionais de monóides parcialmente reversíveis
05/12/2003 Sexta-feira, 05 de Dezembro de 2003, 16h, Anfiteatro
Pedro Ventura Silva
(CMUP, Universidade do Porto, Portugal)
Propomos um novo modelo computacional na teoria de linguagens para abarcar com generalidade situações de reversibilidade parcial. A inovação consiste em substituir o modelo clássico do monóide livre por monóides que admitem inversos (à direita ou bilaterais) para algumas das letras do alfabeto base, e dá origem a produtos livres de monóides livres, grupos livres e monóides bicíclicos. Os principais resultados são a solução do problema da palavra para monóides sintácticos de subconjuntos racionais, e a demonstração de que é decidível se um subconjunto racional é reconhecível.
|