Hipergrafos de Dijkstra: Reconhecimento e Isomorfismo - Cavadas, Leonardo de Almeida (2024)
Um programa de computador frequentemente pode ter seu fluxo de controle representado por meio de grafos direcionados. Dijkstra apresentou os conceitos da programação sequencial estruturada como aquela que não contém a estrutura GO TO. Hetch e Ullman apresentaram os grafos direcionados de fluxo redutível, onde os grafos direcionados associados a um programa sequencial formam uma subclasse própria da classe dos grafos de fluxo redutível e esses grafos direcionados podem representar o fluxo de execução de um programa sequencial estruturado como descrito por Dijkstra. Dijkstra também estabeleceu o conceito de programação estruturada paralela introduzindo o comando PAR- BEGIN/PAREND. Bento et al. caracterizaram a classe dos grafos de Dijkstra os quais correspondem a grafos de fluxo de programas escritos usando programação sequencial estruturada, conforme descrito por Dijkstra. Bento et al. provaram que o reconhecimento desses grafos é linear, bem como a checagem do isomorfismo entre grafos dessa classe. Guedes e Markenzon introduziram o conceito de hipergrafos de fluxo redutível que estende, naturalmente, a classe dos grafos de fluxo redutível. A classe dos hipergrafos de fluxo redutíveis é uma superclasse própria da classe dos grafos de fluxo de programas paralelos estruturados. Nessa dissertação definimos os hipergrafos direcionados de Dijkstra como a classe que caracteriza os grafos de fluxo de programas paralelos estruturados que têm a estrutura paralela PARBEGIN/PAREND. Provamos que o reconhecimento desses hipergrafos é linear, bem como a checagem do isomorfismo entre hipergrafos dessa classe.