Skip to main content
Department of Information Technology

Adjacent ordered Multi pushdown systems

Speaker

Prakash Saivasan, Chennai Mathematical Institute, India

Date and Time

Wednesday, June 11th, 2014 at 14:15.

Location

Polacksbacken, room 4306

Abstract

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.

Updated  2014-06-09 15:50:03 by Mohamed Faouzi Atig.