프로그램 구조 트리

Program structure tree

PST(Program Structure Tree)는 SESE(Single-entry Single-Exit) 조각/지역의 내포 관계를 표시하는 계층형 다이어그램으로 컴퓨터 프로그램의 구성을 보여준다.이 트리의 노드는 프로그램의 SESE 영역을 나타내고, 가장자리는 내포 영역을 나타낸다.PST는 모든 제어 흐름 그래프에 대해 정의된다.

참고문헌장

이 참고문헌에는 프로그램 및/또는 (작업)흐름 그래프의 파싱에 대한 연구에 박차를 가한 중요한 저작물들이 나열되어 있다(섹션 3.5 참조).Polyvyanyy, Artem (2012). Structuring Process Models (Ph.D.). University of Potsdam.).

  • 연결 속성은 그래프의 기본 속성이며 그래프가 평면인지 또는 두 개의 그래프가 이형인지 여부를 판단할 때 유용하다.존 홉크로프트와 로버트 엔드레 타르잔(1973)은 그래프를 트리코넥트 구성요소로 분할하기 위한 최적의 (정수 인자 내) 알고리즘을 개발했다.[1]알고리즘은 그래프의 깊이 우선 검색을 기반으로 하며 정점과 E 가장자리가 있는 그래프를 하려면 + )+ E 의 시간과 공간이 필요하다.
  • Robert Endre Tarjan과 Jacobo Valdes(1980년)는 양방향 흐름 그래프의 구조 분석에 트리코넥트 성분을 사용했다.[2]흐름 그래프의 비방향 버전의 트리코넥트 구성요소는 지시된 흐름 그래프의 구조 정보를 발견하는 데 유용한 것으로 보인다.트리코넥트 구성요소는 효율적으로 발견될 수 있으며 흐름 그래프의 SESE 조각의 계층을 형성한다.
  • 주세페 디 바티스타와 로베르토 타마시아(1990년)는 트리코넥트 성분과 관련하여 바이코넥트 그래프의 분해를 나타내는 데이터 구조인 SPQR-tree를[3] 소개했다.본질적으로 SPQR 트리는 타르잔과 발데스의 파스 나무다.[2]저자들은 다양한 온라인 그래프 알고리즘(예: 전이성 폐쇄, 평면성 테스트, 최소 신장 트리)에 대한 SPQR 트리의 유용성을 보여주었다.[3]특히 저자들은 그래프의 트리코넥트 구성요소의 온라인 유지보수 문제에 대한 효율적인 해결책을 제시했다.[4]
  • 리처드 C.존슨 외 연구진(1994)은 단일 에지 진입과 단일 에지 출구 영역에 기초한 프로그램 구조의 계층적 표현인 PST(프로그램 구조 트리)를 제안했다.[5][6]PST는 임의 흐름 그래프에 대해 () O 시간 단위로 계산할 수 있으며, 여기서 은 그래프에서 가장자리 집합이다.PST의 단점은 가장자리 입력과 출구만을 기반으로 SESE 조각 개념을 이용한다는 것이다.따라서 PST는 정점 입력과 출구를 기반으로 하는 SESE 파편을 캡처하지 않는다.
  • Carsten Gutwenger와 Petra Mutzel(2001)은 서로 연결된 그래프의 트리코넥트 구성요소의 선형 시간 계산에 관한 실무 경험을 공유했다.[7]그들은 에 있는[1] 알고리즘의 결함 부분을 확인하고 수정했으며, 결과 알고리즘을 SPQR-tree의 계산에 적용했다.그 시행은 공개적으로 가능하다.
  • 천우양 외(2006~2009) BPMN 도표를 BPEL 프로세스로 변환하기 위해 파싱을 사용했다.[8][9]한 조각의 채택된 개념은 한 지역의 개념과 유사하다.[5]그러나 개발된 파싱 알고리즘은 결정론적이지 않다. 즉, 파스 트리는 주어진 다이어그램에 대해 고유하지 않다.
  • Jussi Vanhalo 등.(2008-2009)은 정제 공정 구조 트리(RST)를 도입했다.[10][11][12]워크플로우 그래프를 볼 때 RPST는 고유하고 모듈형이며 알려진 다른 파스 트리보다 더 미세하다. 즉, 다른 기술보다 더 많은 SESE 파편을 발견한다.실제로, RPST는 그래프의 모든 SESE 파편을 나타내는 워크플로 그래프의 모든 표준 파편을 캡처한다.RPST는 임의 프로그램/워크플로 그래프를 위해 계산할 수 있다.
  • Artem Polyvyany, Jussi Vanhalo, Hagen Voelzer(2010)는 RPST 계산을 위한 단순화된 알고리즘을 제안했다.[13]이 단순화된 알고리즘은 임의 프로그램/워크플로 그래프의 RPST 계산을 위한 서브루틴으로 간단한 방법으로 사용할 수 있다.원래의 알고리즘과 단순화된 알고리즘 모두 RPST의 효율적인 연산을 가능하게 한다.그러나 표준 SESE 조각의 구조 특성은 다르다.

외부 링크

참조

  1. ^ a b Hopcroft, John; Tarjan, Robert (1973), "Dividing a graph into triconnected components", SIAM Journal on Computing, 2 (3): 135–158, doi:10.1137/0202012, hdl:1813/6037.
  2. ^ a b 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, S2CID 7460037.
  3. ^ a b 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, vol. 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, S2CID 7838334
  5. ^ a b Johnson, Richard Craig; Pearson, David; Pingali, Keshav (1994). "The program structure tree". 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. S2CID 5753565.
  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, vol. 1984, Springer-Verlag, pp. 77–90, doi:10.1007/3-540-44541-2_8, ISBN 978-3-540-41554-1
  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. International/European Conference on Web Services (ICWS). 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, S2CID 7838334
  10. ^ Vanhatalo, Jussi; Voelzer, Hagen; Koehler, Jana (2008), "The refined process structure tree", Business Process Management (BPM), Lecture Notes in Computer Science, vol. 5240, pp. 100–115, CiteSeerX 10.1.1.231.5934, doi:10.1007/978-3-540-85758-7_10, ISBN 978-3-540-85757-0
  11. ^ Vanhatalo, Jussi; Voelzer, Hagen; Koehler, Jana (2009), "The refined process structure tree", Data and Knowledge Engineering, 68 (9): 793–818, CiteSeerX 10.1.1.231.3567, 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. ^ a b 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, vol. 6551, Springer Berlin Heidelberg, pp. 25–41, doi:10.1007/978-3-642-19589-1_2, hdl:11343/224170, ISBN 978-3-642-19588-4