Adjacent ordered Multi pushdown systems
Prakash Saivasan, Chennai Mathematical Institute, India
Date and Time
Wednesday, June 11th, 2014 at 14:15.
Polacksbacken, room 4306
Multi pushdown systems have been well studied. We propose a new multi pushdown model called Adjacent ordered multi-pushdown system (AOMPDS), where values may be pushed only on the lowest non- empty stack or one of its two neighbours and values can only be popped from the lowest non-empty stack. We describe Exptime decision procedures for reachability and LTL model-checking, establish matching lower bounds and describe few applications of this model. This is a joint work with K Narayan Kumar and Mohamed Faouzi Atig.