Program structure tree

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. ).

External links

References

  1. 1 2 Hopcroft, John; Tarjan, Robert (1973), "Dividing a graph into triconnected components", SIAM Journal on Computing, 2 (3): 135–158, doi:10.1137/0202012.
  2. 1 2 Tarjan, Robert; Valdes, Jacobo (1980), Prime subprogram parsing of a program, pp. 95–105, doi:10.1145/567446.567456.
  3. 1 2 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
  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. 1 2 Johnson, Richard Craig; Pearson, David; Pingali, Keshav (1994), The Program Structure Tree: Computing Control Regions in Linear Time, pp. 171–185, doi:10.1145/178243.178258
  6. Johnson, Richard Craig (1995). Efficient Program Analysis using Dependence Flow Graphs (Ph.D.). Cornell University.
  7. Gutwenger, Carsten; Mutzel, Petra (2001), "A linear time implementation of SPQR-trees", Proc. 8th International Symposium on Graph Drawing (GD 2000), Lecture Notes in Computer Science, 1984, Springer-Verlag, pp. 77–90, doi:10.1007/3-540-44541-2_8
  8. Ouyang, Chun; Dumas, Marlon; ter Hofstede, Arthur H. M.; van der Aalst, Wil M. P. (2006), From BPMN process models to BPEL web services, pp. 285–292
  9. 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
  10. Vanhatalo, Jussi; Voelzer, Hagen; Koehler, Jana (2008), The refined process structure tree, pp. 100–115, doi:10.1007/978-3-540-85758-7_10
  11. 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
  12. 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.
  13. 1 2 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
This article is issued from Wikipedia - version of the 1/25/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.