Efficient Algorithms for Alternating Pushdown Systems with an Application to the Computation of Certificate Chains

DOI10.1007/11901914_13zbMATH Open1161.68495OpenAlexW1489658028MaRDI QIDQ3522906FDOQ3522906

Authors: Dejvuth Suwimonteerabuth, Stefan Schwoon, Javier Esparza 

Publication date: 4 September 2008

Published in: Automated Technology for Verification and Analysis (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11901914_13

Recommendations

• Approximability of minimum certificate dispersal with tree structures
• Relationship between Approximability and Request Structures in the Minimum Certificate Dispersal Problem
• Linear-time certifying algorithms for near-graphical sequences
• Certificates and fast algorithms for biconnectivity in fully-dynamic graphs
• Sub-linear Distributed Algorithms for Sparse Certificates and Biconnected Components
• Algorithms for the Certified Write-All Problem
• scientific article; zbMATH DE number 871918
• On certificates and lookahead in dynamic graph problems

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25)

Cited In (6)

• Efficient CTL model-checking for pushdown systems
• Reachability on prefix-recognizable graphs
• An automata-theoretic approach to infinite-state systems
• Efficient CTL model-checking for pushdown systems
• Tools and Algorithms for the Construction and Analysis of Systems
• Relationship between Approximability and Request Structures in the Minimum Certificate Dispersal Problem

This page was built for publication: Efficient Algorithms for Alternating Pushdown Systems with an Application to the Computation of Certificate Chains

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