Room 327

Decidable Aspects Of Parity Games Over Pushdown Systems

Abhijith R Nair

IMSc

The focus of this thesis is on pushdown processes, which are common in programs
that involve recursion. The study investigates the decidability of properties related
to pushdown processes and their transition graphs. We examines structures with
decidable MSO theories and show that the set of transition graphs of pushdown
systems also has a decidable MSO theory. Furthermore we delve into parity games
over pushdown systems, providing algorithms to determine winning strategies for
players in these games as well as determining the winner of parity game. Additionally
it explores parity games over higher order pushdown systems and showing that
determining winner of a higher order pushdown system is decidable as well.

This will be Abhijith's MSc thesis defence.