{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:11:28Z","timestamp":1760202688567},"reference-count":19,"publisher":"World Scientific Pub Co Pte Lt","issue":"08","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2014,12]]},"abstract":"<jats:p> Multi-pushdown systems are formal models of multi-threaded programs. As they are Turing powerful in their full generality, several decidable subclasses, constituting under-approximations of the original system, have been studied in the recent years. Ordered Multi-Pushdown Systems (OMPDSs) impose an order on the stacks and limit pop actions to the lowest non-empty stack. The control state reachability for OMPDSs is 2-ETIME-COMPLETE. We propose a restriction on OMPDSs, called Adjacent OMPDSs (AOMPDS), where values may be pushed only on the lowest non-empty stack or one of its two neighbours. We describe EXPTIME decision procedures for reachability and LTL model-checking and establish matching lower bounds. We demonstrate the utility of this model as an algorithmic tool via optimal reductions from other models. <\/jats:p>","DOI":"10.1142\/s0129054114400255","type":"journal-article","created":{"date-parts":[[2015,2,25]],"date-time":"2015-02-25T01:32:14Z","timestamp":1424827934000},"page":"1083-1096","source":"Crossref","is-referenced-by-count":6,"title":["ADJACENT ORDERED MULTI-PUSHDOWN SYSTEMS"],"prefix":"10.1142","volume":"25","author":[{"given":"MOHAMED FAOUZI","family":"ATIG","sequence":"first","affiliation":[{"name":"Uppsala University, Sweden"}]},{"given":"K. NARAYAN","family":"KUMAR","sequence":"additional","affiliation":[{"name":"Chennai Mathematical Institute, India"}]},{"given":"PRAKASH","family":"SAIVASAN","sequence":"additional","affiliation":[{"name":"Chennai Mathematical Institute, India"}]}],"member":"219","published-online":{"date-parts":[[2015,2,24]]},"reference":[{"key":"p_2","first-page":"121","volume":"5257","author":"Atig M. F.","year":"2008","journal-title":"LNCS"},{"key":"p_3","first-page":"210","volume":"7358","author":"Atig M. F.","year":"2012","journal-title":"LNCS"},{"key":"p_5","first-page":"58","volume":"7907","author":"Atig M. F.","year":"2013","journal-title":"LNCS"},{"key":"p_6","first-page":"132","volume":"6907","author":"Bollig B.","year":"2011","journal-title":"LNCS"},{"key":"p_7","first-page":"348","volume":"3821","author":"Bouajjani A.","year":"2005","journal-title":"LNCS"},{"key":"p_8","first-page":"207","volume":"4590","author":"Bouajjani A.","year":"2007","journal-title":"LNCS"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054196000191"},{"key":"p_10","first-page":"547","volume":"7454","author":"Cyriac A.","year":"2012","journal-title":"LNCS"},{"key":"p_11","first-page":"267","volume":"6014","author":"Heu\u00dfner A.","year":"2010","journal-title":"LNCS"},{"issue":"1","key":"p_12","first-page":"73","volume":"35","author":"Lal A.","year":"2009","journal-title":"FMSD"},{"key":"p_13","first-page":"282","volume":"4963","author":"Lal A.","year":"2008","journal-title":"LNCS"},{"key":"p_14","first-page":"346","volume":"629","author":"Lange K.-J.","year":"1992","journal-title":"LNCS"},{"key":"p_17","first-page":"93","volume":"3440","author":"Qadeer S.","year":"2005","journal-title":"LNCS"},{"key":"p_18","first-page":"615","volume":"6174","author":"Seth A.","year":"2010","journal-title":"LNCS"},{"key":"p_20","first-page":"299","volume":"4963","author":"Torre S. L.","year":"2008","journal-title":"LNCS"},{"key":"p_21","first-page":"33","volume":"5213","author":"Torre S. L.","year":"2008","journal-title":"LNCS"},{"key":"p_22","first-page":"477","volume":"5643","author":"Torre S. L.","year":"2009","journal-title":"LNCS"},{"key":"p_23","first-page":"203","volume":"6901","author":"Torre S. L.","year":"2011","journal-title":"LNCS"},{"key":"p_24","first-page":"225","volume":"7604","author":"Torre S. L.","year":"2012","journal-title":"LNCS"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054114400255","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T11:14:14Z","timestamp":1565176454000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054114400255"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12]]},"references-count":19,"journal-issue":{"issue":"08","published-online":{"date-parts":[[2015,2,24]]},"published-print":{"date-parts":[[2014,12]]}},"alternative-id":["10.1142\/S0129054114400255"],"URL":"https:\/\/doi.org\/10.1142\/s0129054114400255","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12]]}}}