Faster algorithms for the nonemptiness of streett automata and for communication protocol pruning

DOI10.1007/3-540-61422-2_117MaRDI QIDQ5054804zbMATH OpenOpenAlexFDO

Authors Jan Arne Telle, Monika R. Henzinger

Publication date 9 December 2022

Published in Algorithm Theory — SWAT'96 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-61422-2_117

Mathematics Subject Classification ID

Network protocols (68M12) Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• Improved algorithms for one-pair and k-pair Streett objectives
• Improved algorithms for parity and Streett objectives
• An algorithm for strongly connected component analysis in \(n \log n\) symbolic steps
• Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition
• On-the-fly emptiness check of transition-based Streett automata

Cites work

• An On-Line Edge-Deletion Problem
• Depth-First Search and Linear Graph Algorithms
• scientific article; zbMATH DE number 734956 (Why is no real title available?)
• Modalities for model checking: Branching time logic strikes back

Cited in

(6)

• Model checking with fairness assumptions using PAT
• Mechanizing the Powerset Construction for Restricted Classes of ω-Automata
• On-the-fly emptiness check of transition-based Streett automata
• Improved algorithms for one-pair and k-pair Streett objectives
• Near-linear time algorithms for Streett objectives in graphs and MDPs
• On the complexity of rational verification

This page was built for publication: Faster algorithms for the nonemptiness of streett automata and for communication protocol pruning

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