Sistemas de Reescrita
Código
8417
Unidade Orgânica
Faculdade de Ciências e Tecnologia
Departamento
Departamento de Matemática
Créditos
6.0
Professor responsável
António José Mesquita da Cunha Machado Malheiro
Horas semanais
4
Total de horas
16
Língua de ensino
Português
Objectivos
Domínio dos conceitos fundamentais dos sistemas de reescrita, tais como os de terminação e confluência.
Saber provar os resultados básicos da teoria de sistemas de reescrita, entre os quais o teorema dos pares críticos.
Saber aplicar os resultados fundamentais da teoria em apresentações de semigrupos e bases de Grobner.
Reconhecer a aplicação destes conceitos em alguns sistemas computacionais, como por exemplo na computação algébrica simbólica, na prova automática de teoremas, na especificação e verificação de programas e na programação de linguagens de ordens superiores.
Pré-requisitos
Não tem requisitos, embora seja aconselhável para alunos que frequentem uma licenciatura em matemática ou informática ou similares.
Conteúdo
1. Sistemas abstractos de redução: reduções e equivalências; indução transfinita; relações de ordem.
2. Sistemas de reescrita de termos: termos, substituições e identidades; álgebras livres; álgebras de termos; classes equacionais; problemas equacionais.
3. Sistemas de reescrita de palavras: congruências de Church-Rosser; o problema da palavra; semigrupos e apresentações.
4. Terminação: o problema de decisão; ordens de redução; ordens de simplificação.
5. Confluência: confluência e confluência local; o problema de decisão; pares críticos.
6. Completude: o procedimento de Knuth-Bendix.
7. Bases de Grobner: redução de polinómios; bases de Grobner; algoritmo de Buchberger.
Bibliografia
• F. Baader and T. Nipkow. Term Rewriting and All That. Cambridge University Press, 1998.
• B. Benninghofen, S. Kemmerich and M. M. Richter. Systems of Reductions. Lecture Notes in Computer Science, vol. 277. Springer-Verlag, 1987.
• R.V. Book and F. Otto. String-Rewriting Systems. Springer-Verlag, 1993.
• TERESE, Term Rewriting Systems, Cambridge University Press, 2003.
• E. Ohlebusch. Advanced Topics in Term Rewriting. Springer-Verlag, 2002.
Método de ensino
Nas aulas teórico-práticas serão apresentados os principais tópicos e resultados, devendo estes ser complementados com a leitura do livro de referência. Serão propostos exercícios de modo a consolidar o estudo. Os alunos são convidados a apresentar o seu trabalho e as suas dificuldades ao professor durante o horário de dúvidas e também por e-mail.
Método de avaliação
A avaliação de conhecimentos à disciplina de sistemas de reescrita compreende dois modelos. Uma avaliação contínua ou um exame final.
A avaliação contínua tem três momentos. Dois serão provas escritas e o restante um trabalho realizado pelo aluno individualmente. A cada uma destas provas escritas corresponde uma percentagem de 35% da nota final à disciplina, correspondendo 30% ao trabalho individual. Cada prova escrita tem a duração de 120 minutos. Os trabalhos serão apresentados e discutidos em seminário. Cada uma destas provas será cotada de 0 a 20 valores, com precisão à décima. O resultado final será a média ponderada das três provas com arredondamento às unidades.
A avaliação em exame final tem a duração de três horas.
Em qualquer das situações, se a nota final for superior a 16 valores, o aluno pode optar por ficar com nota final de 16 valores ou realizar uma prova complementar/oral para defender a nota.