Hipergrafos de Dijkstra: Reconhecimento e Isomorfismo

Abstract

A computer program’s control flow can often be represented through directed graphs. Dijkstra introduced the concepts of structured sequential programming as one that does not contain the GO TO structure. Hetch and Ullman presented reducible flow directed graphs, where the directed graphs class associated with a sequential program is a proper subclass of the class of reducible flow graphs, and these directed graphs can represent the execution flow of a sequential structured program as described by Dijkstra. Dijkstra also established the concept of parallel structured programming by introducing the PARBEGIN/PAREND command. Bento et al. characterized the class of Dijkstra’s graphs which correspond to flow graphs of programs written using structured sequential programming, as described by Dijkstra. Bento et al. proved that the recognition of these graphs is linear, as well as checking the isomorphism between graphs of this class. Guedes and Markenzon introduced the concept of reducible flow hypergraphs, which naturally extends the class of reducible flow graphs. The class of reducible flow hypergraphs is a superclass of the class of flow graphs of structured parallel programs. In this dissertation, we define Dijkstra’s directed hypergraphs as the class that characterizes the flow graphs of structured parallel programs having the parallel structure PARBEGIN/PAREND. We prove that the recognition of these hypergraphs is linear, as well as checking the iso- morphism between hypergraphs of this class.