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

DOI10.1007/11901914_13MaRDI QIDQ3522906zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cited in

(6)

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

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)