Revisiting underapproximate reachability for multipushdown systems

DOI10.1007/978-3-030-45190-5_21MaRDI QIDQ5039520zbMATH OpenOpenAlexFDO

Authors S. Akshay, Paul Gastin, Shankara Narayanan Krishna, Sparsa Roychowdhury

Publication date 13 October 2022

Published in Tools and Algorithms for the Construction and Analysis of Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2002.05950

zbMATH Keywords

multipushdown systemstimed pushdown automataunderapproximate reachability

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Formal languages and automata (68Q45)

Recommendations

• Reachability of scope-bounded multistack pushdown systems
• Reachability of multistack pushdown systems with scope-bounded matching relations
• Reachability problem for weak multi-pushdown automata
• Reachability problem for weak multi-pushdown automata
• Scope-Bounded Reachability in Valence Systems

Cites work

• A perfect class of context-sensitive timed languages
• Analyzing timed systems using tree automata
• Concurrent manipulation of binary search trees
• Dense-timed pushdown automata
• scientific article; zbMATH DE number 1670769 (Why is no real title available?)
• scientific article; zbMATH DE number 1033414 (Why is no real title available?)
• Introduction to algorithms.
• Model-checking of ordered multi-pushdown automata
• MSO decidability of multi-pushdown systems via split-width
• Reachability of multistack pushdown systems with scope-bounded matching relations
• Scope-bounded multistack pushdown systems: fixed-point, sequentialization, and tree-width
• Scope-bounded pushdown languages
• The language theory of bounded context-switching
• The Minimal Cost Reachability Problem in Priced Timed Pushdown Systems
• The tree width of auxiliary storage
• Tools and Algorithms for the Construction and Analysis of Systems
• Towards an Efficient Tree Automata based technique for Timed Systems
• Visibly pushdown languages

Cited in

(7)

• Acceleration in multi-pushdown systems
• Complexity results for reachability in cooperating systems and approximated reachability by abstract over-approximations
• The Reach-Avoid Problem for Constant-Rate Multi-mode Systems
• Fully Dynamic Single-Source Reachability in Practice: An Experimental Study
• On the complexity of multi-pushdown games
• Model-checking parametric lock-sharing systems against regular constraints
• Fast zone-based algorithms for reachability in pushdown timed automata

Describes a project that uses

Uses Software

• MAGIC

This page was built for publication: Revisiting underapproximate reachability for multipushdown systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5039520)