Дерево структуры программы

Дерево структуры программы (PST) — это иерархическая диаграмма, которая отображает отношения вложенности фрагментов/областей с одним входом и одним выходом (SESE), показывая организацию компьютерной программы . Узлы в этом дереве представляют SESE-регионы программы, а ребра представляют собой вложенные регионы. PST определен для всех графов потока управления.

Библиографические примечания

В этих примечаниях перечислены важные работы, которые стимулировали исследования по синтаксическому анализу программ и/или графов (рабочих) потоков (адаптировано из раздела 3.5 в Поливяный, Артем (2012). Структурирование моделей процессов (доктор философии). Потсдамский университет. ).

Свойства связности являются основными свойствами графов и полезны при проверке того, является ли граф плоским, или при определении изоморфности двух графов. Джон Хопкрофт и Роберт Эндре Тарьян (1973) разработали оптимальный (с точностью до постоянного коэффициента) алгоритм разделения графа на трехсвязные компоненты. ^{[ 1 ]} Алгоритм основан на поиске графов в глубину и требует $O(|V|+|E|)$ время и пространство для изучения графика с $|V|$ вершины и $|E|$ края.
Роберт Эндре Тарьян и Хакобо Вальдес (1980) использовали трехсвязные компоненты для структурного анализа двусвязных потоковых графов. ^{[ 2 ]} Показано, что трехсвязные компоненты неориентированной версии потокового графа полезны для обнаружения структурной информации направленных потоковых графов. Трехсвязные компоненты можно эффективно обнаружить и сформировать иерархию SESE-фрагментов потокового графа.
Джузеппе Ди Баттиста и Роберто Тамассиа (1990) представили SPQR-деревья. ^{[ 3 ]} - структура данных, которая представляет собой разложение двусвязного графа по его трехсвязным компонентам. По сути, SPQR-деревья — это деревья синтаксического анализа Тарьяна и Вальдеса. ^{[ 2 ]} Авторы показали полезность SPQR-деревьев для различных алгоритмов онлайн-графов, например, транзитивного замыкания, проверки планарности и минимального остовного дерева. ^{[ 3 ]} В частности, авторы предложили эффективное решение проблемы оперативного обслуживания трёхсвязных компонент графа. ^{[ 4 ]}
Ричард С. Джонсон и др. (1994) предложили дерево структуры программы (PST), иерархическое представление структуры программы, основанное на областях входа с одним ребром и областях выхода с одним ребром. ^{[ 5 ]}^{[ 6 ]} PST можно рассчитать в $O(|E|)$ время для произвольного графа потока, где $E$ — множество ребер графа. Недостаток PST заключается в том, что он использует понятие SESE-фрагмента, основанного только на пограничных входах и выходах. Таким образом, PST не захватывает те SESE-фрагменты, которые основаны на входах и выходах вершин.
Карстен Гутвенгер и Петра Мутцель (2001) поделились своим практическим опытом вычисления за линейное время трехсвязных компонентов двусвязных графов. ^{[ 7 ]} Они выявили и исправили ошибочные части алгоритма в ^{[ 1 ]} и применил полученный алгоритм к вычислению SPQR-деревьев. Реализация общедоступна.

Чун Оуян и др. (2006–2009) использовали синтаксический анализ для перевода диаграмм BPMN в процессы BPEL. ^{[ 8 ]}^{[ 9 ]} Используемое понятие фрагмента аналогично понятию области в. ^{[ 5 ]} Однако разработанный алгоритм разбора является недетерминированным, т.е. дерево разбора не является уникальным для данной диаграммы.
Юсси Ванхатало и др. (2008–2009) представил усовершенствованное дерево структуры процессов (RPST). ^{[ 10 ]}^{[ 11 ]}^{[ 12 ]} Учитывая граф рабочего процесса, RPST является уникальным, модульным и более детальным, чем любое другое известное дерево синтаксического анализа, т. е. он обнаруживает больше SESE-фрагментов, чем любой другой метод. Фактически, RPST фиксирует все канонические фрагменты графа рабочего процесса, которые, в свою очередь, представляют все SESE-фрагменты графа. RPST можно рассчитать для произвольного графа программы/рабочего процесса. ^{[ нужна ссылка ]}
Артем Поливяный, Юсси Ванхатало и Хаген Фельцер (2010) предложили упрощенный алгоритм расчета RPST. ^{[ 13 ]} Этот упрощенный алгоритм можно напрямую использовать в качестве подпрограммы для вычисления RPST произвольного графа программы/рабочего процесса. Оба алгоритма, исходный и упрощенный, позволяют эффективно вычислить RPST. Однако они дают разные структурные характеристики канонических SESE-фрагментов.

Внешние ссылки

Java-реализация усовершенствованного дерева структуры процессов в библиотеке jBPT (см. класс RPST в модуле jbpt-deco). Реализация следует алгоритму, описанному в ^{[ 13 ]}

Ссылки

^ Перейти обратно: ^а ^б Хопкрофт, Джон ; Тарьян, Роберт (1973), «Разделение графа на трехсвязные компоненты», SIAM Journal on Computing , 2 (3): 135–158, doi : 10.1137/0202012 , hdl : 1813/6037 .
^ Перейти обратно: ^а ^б Тарьян, Роберт ; Вальдес, Хакобо (1980), «Разбор простых подпрограмм программы», Труды 7-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования - POPL '80 , стр. 95–105, doi : 10.1145/567446.567456 , ISBN 978-0897910118 , S2CID 7460037 .
^ Перейти обратно: ^а ^б Ди Баттиста, Джузеппе; Тамассиа, Роберто (1990), «Алгоритмы онлайн-графов с SPQR-деревьями», Proc. 17-й Международный коллоквиум по автоматам, языкам и программированию , Конспекты лекций по информатике, том. 443, Springer-Verlag, стр. 598–611 , doi : 10.1007/BFb0032061 , ISBN. 978-3-540-52826-5
^ Ди Баттиста, Джузеппе; Тамассиа, Роберто (1996), «Онлайн-обслуживание трехсвязных компонентов с помощью SPQR-деревьев», Algorithmica , 15 (4): 302–318, doi : 10.1007/BF01961541 , S2CID 7838334
^ Перейти обратно: ^а ^б Джонсон, Ричард Крейг; Пирсон, Дэвид; Пингали, Кешав (1994). «Дерево структуры программы». Дерево структуры программы: вычисление контрольных областей за линейное время . Конференция SIGPLAN по проектированию и реализации языков программирования (PLDI). стр. 171–185. дои : 10.1145/178243.178258 . ISBN 978-0897916622 . S2CID 5753565 .
^ Джонсон, Ричард Крейг (1995). Эффективный анализ программ с использованием графов потоков зависимостей (доктор философии). Корнелльский университет.
^ Гутвенгер, Карстен; Мутцель, Петра (2001), «Реализация SPQR-деревьев с линейным временем», Proc. 8-й Международный симпозиум по рисованию графов (GD 2000) , Конспекты лекций по информатике, том. 1984, Springer-Verlag, стр. 77–90, номер документа : 10.1007/3-540-44541-2_8 , ISBN. 978-3-540-41554-1
^ Оуян, Чун; Дюма, Марлон; тер Хофстеде, Артур Х.М.; ван дер Аалст, Вил член парламента (2006). От моделей процессов BPMN до веб-сервисов BPEL . Международная/Европейская конференция по веб-сервисам (ICWS). стр. 285–292.
^ Оуян, Чун; Дюма, Марлон; ван дер Аалст, член парламента Вила; тер Хофстеде, Артур Х.М.; Мендлинг, январь (2009 г.), «От моделей бизнес-процессов к процессно-ориентированным программным системам», ACM Transactions on Software Engineering and Methodology , 19 (1): 2:1–2:37, doi : 10.1007/BF01961541 , S2CID 7838334
^ Ванхатало, Юсси; Фельцер, Хаген; Келер, Яна (2008), «Уточненное дерево структуры процессов», Управление бизнес-процессами (BPM) , Конспекты лекций по информатике, том. 5240, стр. 100–115, CiteSeerX 10.1.1.231.5934 , doi : 10.1007/978-3-540-85758-7_10 , ISBN 978-3-540-85757-0
^ Ванхатало, Юсси; Фельцер, Хаген; Келер, Яна (2009), «Уточненное дерево структуры процесса», Data and Knowledge Engineering , 68 (9): 793–818, CiteSeerX 10.1.1.231.3567 , doi : 10.1016/j.datak.2009.02.015
^ Ванхатало, Юсси (2009). Деревья структуры процессов: разложение модели бизнес-процесса на иерархию фрагментов с одним входом-один выходом (доктор философии). Университет Штутгарта.
^ Перейти обратно: ^а ^б Поливяный, А.; Ванхатало, Дж.; Вёльцер, Х. (2010), «Упрощенные вычисления и обобщение уточненного дерева структуры процессов», Веб-сервисы и формальные методы , Конспекты лекций по информатике, том. 6551, Springer Berlin Heidelberg, стр. 25–41, doi : 10.1007/978-3-642-19589-1_2 , hdl : 11343/224170 , ISBN 978-3-642-19588-4 , S2CID 46111591

[HopcroftT73-1] Перейти обратно: ^а ^б Хопкрофт, Джон ; Тарьян, Роберт (1973), «Разделение графа на трехсвязные компоненты», SIAM Journal on Computing , 2 (3): 135–158, doi : 10.1137/0202012 , hdl : 1813/6037 .

[TarjanV80-2] Перейти обратно: ^а ^б Тарьян, Роберт ; Вальдес, Хакобо (1980), «Разбор простых подпрограмм программы», Труды 7-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования - POPL '80 , стр. 95–105, doi : 10.1145/567446.567456 , ISBN 978-0897910118 , S2CID 7460037 .

[BattistaT90-3] Перейти обратно: ^а ^б Ди Баттиста, Джузеппе; Тамассиа, Роберто (1990), «Алгоритмы онлайн-графов с SPQR-деревьями», Proc. 17-й Международный коллоквиум по автоматам, языкам и программированию , Конспекты лекций по информатике, том. 443, Springer-Verlag, стр. 598–611 , doi : 10.1007/BFb0032061 , ISBN. 978-3-540-52826-5

[4] Ди Баттиста, Джузеппе; Тамассиа, Роберто (1996), «Онлайн-обслуживание трехсвязных компонентов с помощью SPQR-деревьев», Algorithmica , 15 (4): 302–318, doi : 10.1007/BF01961541 , S2CID 7838334

[JohnsonPP94-5] Перейти обратно: ^а ^б Джонсон, Ричард Крейг; Пирсон, Дэвид; Пингали, Кешав (1994). «Дерево структуры программы». Дерево структуры программы: вычисление контрольных областей за линейное время . Конференция SIGPLAN по проектированию и реализации языков программирования (PLDI). стр. 171–185. дои : 10.1145/178243.178258 . ISBN 978-0897916622 . S2CID 5753565 .

[6] Джонсон, Ричард Крейг (1995). Эффективный анализ программ с использованием графов потоков зависимостей (доктор философии). Корнелльский университет.

[7] Гутвенгер, Карстен; Мутцель, Петра (2001), «Реализация SPQR-деревьев с линейным временем», Proc. 8-й Международный симпозиум по рисованию графов (GD 2000) , Конспекты лекций по информатике, том. 1984, Springer-Verlag, стр. 77–90, номер документа : 10.1007/3-540-44541-2_8 , ISBN. 978-3-540-41554-1

[8] Оуян, Чун; Дюма, Марлон; тер Хофстеде, Артур Х.М.; ван дер Аалст, Вил член парламента (2006). От моделей процессов BPMN до веб-сервисов BPEL . Международная/Европейская конференция по веб-сервисам (ICWS). стр. 285–292.

[9] Оуян, Чун; Дюма, Марлон; ван дер Аалст, член парламента Вила; тер Хофстеде, Артур Х.М.; Мендлинг, январь (2009 г.), «От моделей бизнес-процессов к процессно-ориентированным программным системам», ACM Transactions on Software Engineering and Methodology , 19 (1): 2:1–2:37, doi : 10.1007/BF01961541 , S2CID 7838334

[10] Ванхатало, Юсси; Фельцер, Хаген; Келер, Яна (2008), «Уточненное дерево структуры процессов», Управление бизнес-процессами (BPM) , Конспекты лекций по информатике, том. 5240, стр. 100–115, CiteSeerX 10.1.1.231.5934 , doi : 10.1007/978-3-540-85758-7_10 , ISBN 978-3-540-85757-0

[11] Ванхатало, Юсси; Фельцер, Хаген; Келер, Яна (2009), «Уточненное дерево структуры процесса», Data and Knowledge Engineering , 68 (9): 793–818, CiteSeerX 10.1.1.231.3567 , doi : 10.1016/j.datak.2009.02.015

[12] Ванхатало, Юсси (2009). Деревья структуры процессов: разложение модели бизнес-процесса на иерархию фрагментов с одним входом-один выходом (доктор философии). Университет Штутгарта.

[PolyvyanyyVV10-13] Перейти обратно: ^а ^б Поливяный, А.; Ванхатало, Дж.; Вёльцер, Х. (2010), «Упрощенные вычисления и обобщение уточненного дерева структуры процессов», Веб-сервисы и формальные методы , Конспекты лекций по информатике, том. 6551, Springer Berlin Heidelberg, стр. 25–41, doi : 10.1007/978-3-642-19589-1_2 , hdl : 11343/224170 , ISBN 978-3-642-19588-4 , S2CID 46111591

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]