Program structure tree

From HandWiki
Revision as of 21:33, 6 February 2024 by Steve Marsio (talk | contribs) (change)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

A program structure tree (PST) is a hierarchical diagram that displays the nesting relationship of single-entry single-exit (SESE) fragments/regions, showing the organization of a computer program. Nodes in this tree represent SESE regions of the program, while edges represent nesting regions. The PST is defined for all control flow graphs.

Bibliographical notes

These notes list important works which fueled research on parsing of programs and/or (work)flow graphs (adapted from Section 3.5 in Polyvyanyy, Artem (2012). Structuring Process Models (Ph.D.). University of Potsdam.).

  • The connectivity properties are the basic properties of graphs and are useful when testing whether a graph is planar or when determining if two graphs are isomorphic. John Hopcroft and Robert Endre Tarjan (1973) developed an optimal (to within a constant factor) algorithm for dividing a graph into triconnected components.[1] The algorithm is based on the depth-first search of graphs and requires [math]\displaystyle{ O(|V|+|E|) }[/math] time and space to examine a graph with [math]\displaystyle{ |V| }[/math] vertices and [math]\displaystyle{ |E| }[/math] edges.
  • Robert Endre Tarjan and Jacobo Valdes (1980) used triconnected components for structural analysis of biconnected flow graphs.[2] The triconnected components of the undirected version of a flow graph are shown to be useful for discovering structural information of directed flow graphs. The triconnected components can be discovered efficiently and form a hierarchy of SESE fragments of a flow graph.
  • Giuseppe Di Battista and Roberto Tamassia (1990) introduced SPQR-trees[3] - a data structure which represents decomposition of a biconnected graph with respect to its triconnected components. Essentially, SPQR-trees are the parse trees of Tarjan and Valdes.[2] The authors showed the usefulness of SPQR-trees for various on-line graph algorithms, e.g., transitive closure, planarity testing, and minimum spanning tree.[3] In particular, the authors proposed an efficient solution to the problem of on-line maintenance of the triconnected components of a graph.[4]
  • Richard C. Johnson et al. (1994) proposed a program structure tree (PST), a hierarchical representation of program structure based on single edge entry and single edge exit regions.[5][6] The PST can be computed in [math]\displaystyle{ O(|E|) }[/math] time for an arbitrary flow graph, where [math]\displaystyle{ E }[/math] is the set of edges in the graph. The disadvantage of the PST is that it exploits the notion of a SESE fragment based on edge entries and exits only. Thus, the PST does not capture those SESE fragments which are based on vertex entries and exits.
  • Carsten Gutwenger and Petra Mutzel (2001) shared their practical experience on linear time computation of the triconnected components of biconnected graphs.Cite error: Closing </ref> missing for <ref> tag[7] The employed notion of a fragment is similar to the notion of a region in.[5] However, the developed parsing algorithm is non-deterministic, i.e., the parse tree is not unique for a given diagram.
  • Jussi Vanhatalo et al. (2008–2009) introduced the Refined Process Structure Tree (RPST).[8][9][10] Given a workflow graph, the RPST is unique, modular, and is finer grained than any other known parse tree, i.e., it discovers more SESE fragments than any other technique. In fact, the RPST captures all canonical fragments of a workflow graph which, in turn, represent all SESE fragments of the graph. The RPST can be computed for an arbitrary program/workflow graph.[citation needed]
  • Artem Polyvyanyy, Jussi Vanhatalo, and Hagen Voelzer (2010) proposed a simplified algorithm for computation of the RPST.[11] This simplified algorithm can be employed in a straightforward way as a subroutine for computation of the RPST of an arbitrary program/workflow graph. Both algorithms, the original and the simplified one, allow for an efficient computation of the RPST. However, they provide different structural characterizations of canonical SESE fragments.

External links

References

  1. ↑ Hopcroft, John; Tarjan, Robert (1973), "Dividing a graph into triconnected components", SIAM Journal on Computing 2 (3): 135–158, doi:10.1137/0202012 .
  2. ↑ 2.0 2.1 Tarjan, Robert; Valdes, Jacobo (1980), "Prime subprogram parsing of a program", Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '80, pp. 95–105, doi:10.1145/567446.567456, ISBN 978-0897910118 .
  3. ↑ 3.0 3.1 Di Battista, Giuseppe; Tamassia, Roberto (1990), "On-line graph algorithms with SPQR-trees", Proc. 17th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, 443, Springer-Verlag, pp. 598–611, doi:10.1007/BFb0032061, ISBN 978-3-540-52826-5 
  4. ↑ Di Battista, Giuseppe; Tamassia, Roberto (1996), "On-line maintenance of triconnected components with SPQR-trees", Algorithmica 15 (4): 302–318, doi:10.1007/BF01961541 
  5. ↑ 5.0 5.1 Johnson, Richard Craig; Pearson, David; Pingali, Keshav (1994). "The Program Structure Tree: Computing Control Regions in Linear Time". SIGPLAN Conference on Programming Language Design and Implementation (PLDI). pp. 171–185. doi:10.1145/178243.178258. ISBN 978-0897916622. 
  6. ↑ Johnson, Richard Craig (1995). Efficient Program Analysis using Dependence Flow Graphs (Ph.D.). Cornell University.
  7. ↑ Ouyang, Chun; Dumas, Marlon; van der Aalst, Wil M. P.; ter Hofstede, Arthur H. M.; Mendling, Jan (2009), "From business process models to process-oriented software systems", ACM Transactions on Software Engineering and Methodology 19 (1): 2:1–2:37, doi:10.1007/BF01961541 
  8. ↑ Vanhatalo, Jussi; Voelzer, Hagen; Koehler, Jana (2008), "The refined process structure tree", Business Process Management (BPM), Lecture Notes in Computer Science, 5240, pp. 100–115, doi:10.1007/978-3-540-85758-7_10, ISBN 978-3-540-85757-0 
  9. ↑ Vanhatalo, Jussi; Voelzer, Hagen; Koehler, Jana (2009), "The refined process structure tree", Data and Knowledge Engineering 68 (9): 793–818, doi:10.1016/j.datak.2009.02.015 
  10. ↑ Vanhatalo, Jussi (2009). Process Structure Trees: Decomposing a Business Process Model into a Hierarchy of Single-Entry-Single-Exit Fragments (Ph.D.). University of Stuttgart.
  11. ↑ 11.0 11.1 Polyvyanyy, A.; Vanhatalo, J.; Völzer, H. (2010), "Simplified Computation and Generalization of the Refined Process Structure Tree", Web Services and Formal Methods, Lecture Notes in Computer Science, 6551, Springer Berlin Heidelberg, pp. 25–41, doi:10.1007/978-3-642-19589-1_2, ISBN 978-3-642-19588-4, http://domino.watson.ibm.com/library/cyberdig.nsf/1e4115aea78b6e7c85256b360066f0d4/e15d645190e222888525764800305d25?OpenDocument 



Retrieved from "https://handwiki.org/wiki/index.php?title=Program_structure_tree&oldid=3381752"