Семинар "Хорошо структурированные магазины"

Докладчик: профессор Мицухито Огава (Mizuhito Ogawa), JAIST (Высшая школа информатики, Япония).

Доклад: Хорошо структурированные магазины (Well structured pushdown systems)

Аннотация
Исторически магазины (PDSs) использовались для моделирования однопотоковых рекурсивных программ, тогда как хорошо структурированные системы переходов (WSTSs) например, Vector Addition Systems (VASs), полезны для представления нерекурсивных многопотоковых программ. На основе этих двух идей мы ставили себе задачу исследовать хорошо структурированные магазины (WSPDSs), магазины с хорошо квази-упорядоченными контролируемыми состояниями и стековым алфавитом. В докладе мы расскажем подклассе WSPDS у которого покрываемость является разрешимым свойством. Также. мы применим технику из WSTS к классическим P-автоматам.

Семинар состоится 17 марта в 11 часов в Семинарской комнате ИСИ СО РАН (к. 254).