Publicado em: 25/01/2012

Tese de Doutorado em Engenharia de Software

UNIVERSIDADE FEDERAL DO RIO GRANDE DO SUL
INSTITUTO DE INFORMÁTICA
PROGRAMA DE POS-GRADUAÇÃO EM COMPUTAÇÃO
———————————————————
DEFESA DE TESE DE DOUTORADO

Aluno: Rodrigo Machado
Orientador: Profa. Dra. Leila Ribeiro
Coorientador: Prof. Dr. Reiko Heckel – University of Leicester (Reino Unido)

Título: Sistemas de Reescrita de Grafos de Alta Ordem

Linha de Pesquisa: Engenharia de Software

Data: 27/01/2012
Hora: 13h30min
Local: Sala ANFV (Anfiteatro Vermelho). Prédio 43412 – Instituto de Informática

Banca Examinadora:
Prof. Dr. Alfio Ricardo de Brito Martini – PUCRS
Prof. Dr. Álvaro Freitas Moreira – UFRGS
Prof. Dr. Roberto da Silva Bigonha – UFMG

Presidente da Banca: Profa. Dra. Leila Ribeiro

Resumo:
A evolução de um software pode ter várias causas: correção de erros, inclusão de novas funcionalidades ou até mesmo, como é o caso de programas orientados a aspectos, transformações estruturais podem fazer parte da semântica do sistema. Apesar de modificações serem comuns, não é tarefa trivial prever como estas afetam o comportamento inicial dos programas, já que os componentes de software normalmente interagem de forma complexa, o que faz com que mesmo pequenas alterações possam introduzir comportamentos indesejados.
A transformação de grafos, também conhecida como reescrita de grafos, é um importante paradigma para modelagem e análise de sistemas. Modelos baseados em transformação de grafos, como gramáticas de grafos, permitem uma modelagem ao mesmo tempo intuitiva e com semântica precisa, permitindo a aplicação de técnicas de análise como verificação de modelos e análise de par crítico. A teoria por trás de transformação de grafos vem sendo desenvolvida a várias décadas, e atualmente está descrita de uma forma bastante genérica. Contudo, ainda não possui uma definição natural de reescritas de alta ordem, o que facilitaria a definição de evolução de especificações compostas por regras de reescrita.
Nesta tese são abordadas a modelagem e a análise de sistemas sob modificações programadas no contexto de gramáticas de grafos. A generalização da abordagem de pushout duplo para reescrita de grafos é utilizada como o princípio geral para descrever, simultaneamente, a semântica do sistema e modificações estruturais. Para tal, introduzimos uma noção de reescrita de segunda ordem para modificar a estrutura de regras de tranformação de grafos, e usando isso, definimos modelos equipados simultaneamente de regras de primeira e segunda ordem, chamados gramáticas de grafos de segunda ordem. Através destes modelos podemos representar simultaneamente transformações estruturais e execução do sistema, e relacionar formalmente ambos tipos de reescrita.
Também propomos novas técnicas para investigar o efeito da modificação de regras sobre a aplicação destas. Finalmente, como um exemplo de aplicação da teoria, caracterizamos construções de sistemas orientados a aspectos através de gramáticas de grafos de segunda ordem, e discutimos como utilizá-las para estudar o efeito da combinação aspectual sobre o sistema inicial.

Palavras-Chave: Sistemas de Transformação de Grafos, Abordagem de Pushout Duplo, Funções de Alta Ordem, Modelagem Orientada a Aspectos, Métodos Formais