253:(2001) shared their practical experience on linear time computation of the triconnected components of biconnected graphs. They have identified and corrected the faulty parts of the algorithm in and applied the resulting algorithm to the computation of SPQR-trees. The implementation is publicly available.
266:
Artem
Polyvyanyy, Jussi Vanhatalo, and Hagen Voelzer (2010) proposed a simplified algorithm for computation of the RPST. 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
262:
Jussi
Vanhatalo et al. (2008–2009) introduced the Refined Process Structure Tree (RPST). 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
177:
Robert Endre Tarjan and Jacobo Valdes (1980) used triconnected components for structural analysis of biconnected flow graphs. 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
58:
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
181:
Giuseppe Di
Battista and Roberto Tamassia (1990) introduced SPQR-trees - 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. The authors showed the usefulness of
258:
Chun Ouyang et al. (2006–2009) used parsing to translate BPMN diagrams into BPEL processes. The employed notion of a fragment is similar to the notion of a region in. However, the developed parsing algorithm is non-deterministic, i.e., the parse tree is not unique for a given
182:
SPQR-trees for various on-line graph algorithms, e.g., transitive closure, planarity testing, and minimum spanning tree. In particular, the authors proposed an efficient solution to the problem of on-line maintenance of the triconnected components of a graph.
245:
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
185:
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. The PST can be computed in
402:
593:
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",
112:
223:
724:
172:
142:
267:
and the simplified one, allow for an efficient computation of the RPST. However, they provide different structural characterizations of canonical SESE fragments.
243:
263:
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.
543:
752:
654:
563:
424:
497:
370:
723:
Polyvyanyy, A.; Vanhatalo, J.; Völzer, H. (2010), "Simplified
Computation and Generalization of the Refined Process Structure Tree",
44:
These notes list important works which fueled research on parsing of programs and/or (work)flow graphs (adapted from
Section 3.5 in
786:
781:
707:
Process
Structure Trees: Decomposing a Business Process Model into a Hierarchy of Single-Entry-Single-Exit Fragments
280:
in the jBPT library (see RPST class in jbpt-deco module). The implementation follows the algorithm described in
25:
678:
632:
353:
Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on
Principles of programming languages - POPL '80
683:
637:
33:
758:
729:, Lecture Notes in Computer Science, vol. 6551, Springer Berlin Heidelberg, pp. 25–41,
610:
503:
484:. SIGPLAN Conference on Programming Language Design and Implementation (PLDI). pp. 171–185.
460:
376:
59:
triconnected components. The algorithm is based on the depth-first search of graphs and requires
408:
178:
components can be discovered efficiently and form a hierarchy of SESE fragments of a flow graph.
62:
748:
669:
Vanhatalo, Jussi; Voelzer, Hagen; Koehler, Jana (2009), "The refined process structure tree",
650:
627:
Vanhatalo, Jussi; Voelzer, Hagen; Koehler, Jana (2008), "The refined process structure tree",
559:
493:
480:
Johnson, Richard Craig; Pearson, David; Pingali, Keshav (1994). "The program structure tree".
420:
366:
738:
730:
688:
642:
602:
549:
485:
452:
440:
412:
398:
356:
325:
317:
189:
29:
578:
Ouyang, Chun; Dumas, Marlon; ter
Hofstede, Arthur H. M.; van der Aalst, Wil M. P. (2006).
147:
117:
47:
522:
228:
548:, Lecture Notes in Computer Science, vol. 1984, Springer-Verlag, pp. 77–90,
775:
348:
305:
301:
762:
614:
539:
507:
464:
380:
250:
21:
32:. Nodes in this tree represent SESE regions of the program, while edges represent
646:
734:
692:
407:, Lecture Notes in Computer Science, vol. 443, Springer-Verlag, pp.
582:. International/European Conference on Web Services (ICWS). pp. 285–292.
554:
489:
443:(1996), "On-line maintenance of triconnected components with SPQR-trees",
404:
Proc. 17th International Colloquium on Automata, Languages and Programming
361:
743:
631:, Lecture Notes in Computer Science, vol. 5240, pp. 100–115,
606:
456:
416:
330:
482:
The Program Structure Tree: Computing Control Regions in Linear Time
321:
277:
351:; Valdes, Jacobo (1980), "Prime subprogram parsing of a program",
545:
Proc. 8th International Symposium on Graph Drawing (GD 2000)
308:(1973), "Dividing a graph into triconnected components",
278:
Java implementation of the Refined Process Structure Tree
36:
regions. The PST is defined for all control flow graphs.
595:
ACM Transactions on Software Engineering and Methodology
28:(SESE) fragments/regions, showing the organization of a
524:
Efficient Program Analysis using Dependence Flow Graphs
542:(2001), "A linear time implementation of SPQR-trees",
231:
192:
150:
120:
65:
401:(1990), "On-line graph algorithms with SPQR-trees",
237:
217:
166:
136:
106:
24:diagram that displays the nesting relationship of
718:
716:
580:From BPMN process models to BPEL web services
475:
473:
392:
390:
296:
294:
8:
343:
341:
742:
682:
636:
553:
360:
329:
230:
207:
199:
191:
159:
151:
149:
129:
121:
119:
96:
88:
80:
72:
64:
225:time for an arbitrary flow graph, where
290:
114:time and space to examine a graph with
7:
14:
709:(Ph.D.). University of Stuttgart.
629:Business Process Management (BPM)
726:Web Services and Formal Methods
521:Johnson, Richard Craig (1995).
52:(Ph.D.). University of Potsdam.
671:Data and Knowledge Engineering
212:
208:
200:
196:
160:
152:
130:
122:
101:
97:
89:
81:
73:
69:
1:
647:10.1007/978-3-540-85758-7_10
527:(Ph.D.). Cornell University.
735:10.1007/978-3-642-19589-1_2
693:10.1016/j.datak.2009.02.015
803:
107:{\displaystyle O(|V|+|E|)}
49:Structuring Process Models
46:Polyvyanyy, Artem (2012).
705:Vanhatalo, Jussi (2009).
310:SIAM Journal on Computing
26:single-entry single-exit
787:Trees (data structures)
555:10.1007/3-540-44541-2_8
439:Di Battista, Giuseppe;
397:Di Battista, Giuseppe;
782:Programming constructs
249:Carsten Gutwenger and
239:
219:
218:{\displaystyle O(|E|)}
168:
138:
108:
18:program structure tree
490:10.1145/178243.178258
362:10.1145/567446.567456
240:
220:
169:
139:
109:
40:Bibliographical notes
538:Gutwenger, Carsten;
229:
190:
148:
118:
63:
355:, pp. 95–105,
167:{\displaystyle |E|}
137:{\displaystyle |V|}
607:10.1007/BF01961541
457:10.1007/BF01961541
417:10.1007/BFb0032061
235:
215:
164:
134:
104:
754:978-3-642-19588-4
656:978-3-540-85757-0
565:978-3-540-41554-1
441:Tamassia, Roberto
426:978-3-540-52826-5
399:Tamassia, Roberto
238:{\displaystyle E}
794:
766:
765:
746:
720:
711:
710:
702:
696:
695:
686:
666:
660:
659:
640:
624:
618:
617:
590:
584:
583:
575:
569:
568:
557:
535:
529:
528:
518:
512:
511:
477:
468:
467:
436:
430:
429:
394:
385:
383:
364:
345:
336:
334:
333:
298:
244:
242:
241:
236:
224:
222:
221:
216:
211:
203:
173:
171:
170:
165:
163:
155:
143:
141:
140:
135:
133:
125:
113:
111:
110:
105:
100:
92:
84:
76:
53:
30:computer program
802:
801:
797:
796:
795:
793:
792:
791:
772:
771:
770:
769:
755:
722:
721:
714:
704:
703:
699:
684:10.1.1.231.3567
668:
667:
663:
657:
638:10.1.1.231.5934
626:
625:
621:
601:(1): 2:1–2:37,
592:
591:
587:
577:
576:
572:
566:
537:
536:
532:
520:
519:
515:
500:
479:
478:
471:
438:
437:
433:
427:
396:
395:
388:
373:
347:
346:
339:
322:10.1137/0202012
300:
299:
292:
287:
274:
227:
226:
188:
187:
146:
145:
116:
115:
61:
60:
45:
42:
12:
11:
5:
800:
798:
790:
789:
784:
774:
773:
768:
767:
753:
712:
697:
677:(9): 793–818,
661:
655:
619:
585:
570:
564:
530:
513:
499:978-0897916622
498:
469:
451:(4): 302–318,
431:
425:
386:
372:978-0897910118
371:
349:Tarjan, Robert
337:
316:(3): 135–158,
306:Tarjan, Robert
302:Hopcroft, John
289:
288:
286:
283:
282:
281:
273:
272:External links
270:
269:
268:
264:
260:
255:
254:
247:
234:
214:
210:
206:
202:
198:
195:
183:
179:
175:
162:
158:
154:
132:
128:
124:
103:
99:
95:
91:
87:
83:
79:
75:
71:
68:
41:
38:
13:
10:
9:
6:
4:
3:
2:
799:
788:
785:
783:
780:
779:
777:
764:
760:
756:
750:
745:
740:
736:
732:
728:
727:
719:
717:
713:
708:
701:
698:
694:
690:
685:
680:
676:
672:
665:
662:
658:
652:
648:
644:
639:
634:
630:
623:
620:
616:
612:
608:
604:
600:
596:
589:
586:
581:
574:
571:
567:
561:
556:
551:
547:
546:
541:
540:Mutzel, Petra
534:
531:
526:
525:
517:
514:
509:
505:
501:
495:
491:
487:
483:
476:
474:
470:
466:
462:
458:
454:
450:
446:
442:
435:
432:
428:
422:
418:
414:
410:
406:
405:
400:
393:
391:
387:
382:
378:
374:
368:
363:
358:
354:
350:
344:
342:
338:
332:
327:
323:
319:
315:
311:
307:
303:
297:
295:
291:
284:
279:
276:
275:
271:
265:
261:
257:
256:
252:
248:
232:
204:
193:
184:
180:
176:
156:
144:vertices and
126:
93:
85:
77:
66:
57:
56:
55:
51:
50:
39:
37:
35:
31:
27:
23:
19:
744:11343/224170
725:
706:
700:
674:
670:
664:
628:
622:
598:
594:
588:
579:
573:
544:
533:
523:
516:
481:
448:
445:Algorithmica
444:
434:
403:
352:
313:
309:
251:Petra Mutzel
48:
43:
22:hierarchical
17:
15:
20:(PST) is a
776:Categories
285:References
679:CiteSeerX
633:CiteSeerX
331:1813/6037
763:46111591
259:diagram.
615:7838334
508:5753565
465:7838334
409:598–611
381:7460037
34:nesting
761:
751:
681:
653:
635:
613:
562:
506:
496:
463:
423:
379:
369:
246:exits.
174:edges.
759:S2CID
611:S2CID
504:S2CID
461:S2CID
377:S2CID
749:ISBN
651:ISBN
560:ISBN
494:ISBN
421:ISBN
367:ISBN
739:hdl
731:doi
689:doi
643:doi
603:doi
550:doi
486:doi
453:doi
413:doi
357:doi
326:hdl
318:doi
54:).
778::
757:,
747:,
737:,
715:^
687:,
675:68
673:,
649:,
641:,
609:,
599:19
597:,
558:,
502:.
492:.
472:^
459:,
449:15
447:,
419:,
411:,
389:^
375:,
365:,
340:^
324:,
312:,
304:;
293:^
16:A
741::
733::
691::
645::
605::
552::
510:.
488::
455::
415::
384:.
359::
335:.
328::
320::
314:2
233:E
213:)
209:|
205:E
201:|
197:(
194:O
161:|
157:E
153:|
131:|
127:V
123:|
102:)
98:|
94:E
90:|
86:+
82:|
78:V
74:|
70:(
67:O
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.