Alexander Heussner ; Jérôme Leroux ; Anca Muscholl ; Grégoire Sutre - Reachability Analysis of Communicating Pushdown Systems

lmcs:921 - Logical Methods in Computer Science, September 27, 2012, Volume 8, Issue 3 - https://doi.org/10.2168/LMCS-8(3:23)2012
Reachability Analysis of Communicating Pushdown Systems

Authors: Alexander Heussner ; Jérôme Leroux ; Anca Muscholl ; Grégoire Sutre

    The reachability analysis of recursive programs that communicate asynchronously over reliable FIFO channels calls for restrictions to ensure decidability. Our first result characterizes communication topologies with a decidable reachability problem restricted to eager runs (i.e., runs where messages are either received immediately after being sent, or never received). The problem is EXPTIME-complete in the decidable case. The second result is a doubly exponential time algorithm for bounded context analysis in this setting, together with a matching lower bound. Both results extend and improve previous work from La Torre et al.


    Volume: Volume 8, Issue 3
    Published on: September 27, 2012
    Accepted on: June 25, 2015
    Submitted on: December 15, 2010
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Formal Languages and Automata Theory,D.2.4, F.2

    Linked data

    Source : ScholeXplorer IsCitedBy ARXIV 2206.11756
    Source : ScholeXplorer IsCitedBy DOI 10.4230/lipics.mfcs.2022.71
    Source : ScholeXplorer IsCitedBy DOI 10.48550/arxiv.2206.11756
    • 10.48550/arxiv.2206.11756
    • 10.4230/lipics.mfcs.2022.71
    • 2206.11756
    Membership Problems in Finite Groups
    Lohrey, Markus ; Rosowski, Andreas ; Zetzsche, Georg ;

    10 Documents citing this article

    Share

    Consultation statistics

    This page has been seen 457 times.
    This article's PDF has been downloaded 221 times.