Incremental dead state detection in logarithmic time

DOI10.1007/978-3-031-37703-7_12zbMATH Open1545.68073MaRDI QIDQ6535537

Margus Veanes, Caleb Stanford

Publication date: 12 January 2024

zbMATH Keywords

online algorithmsgraph algorithmsSMTdead-state detection

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Specification and verification (program logics, model checking, etc.) (68Q60) Graph algorithms (graph-theoretic aspects) (05C85) Online algorithms; streaming algorithms (68W27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Erratum to ``Acyclic automata and small expressions using multi-tilde-bar operators [Theoret. Comput. Sci. 411 (38-39) (2010) 3423-3435]
• Partial derivatives of regular expressions and finite automaton constructions
• An O(n \text{log} n) implementation of the standard method for minimizing n-state finite automata
• An SMT solver for regular expressions and linear arithmetic over string length
• A data structure for dynamic trees
• Maintaining a topological order under edge insertions
• Minimisation of automata
• Advanced automata minimization
• Maintaining information in fully dynamic trees with top trees
• A Decision Procedure for Regular Membership and Length Constraints over Unbounded Strings
• Symbolic Solving of Extended Regular Expression Inequalities.
• Randomized fully dynamic graph algorithms with polylogarithmic time per operation
• Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance
• A dynamic topological sort algorithm for directed acyclic graphs
• Improved Dynamic Reachability Algorithms for Directed Graphs
• Efficient E-Matching for SMT Solvers
• Three Partition Refinement Algorithms
• Fast Decision Procedures Based on Congruence Closure
• Variations on the Common Subexpression Problem
• Efficiency of a Good But Not Linear Set Union Algorithm
• A Data Structure for Dynamically Maintaining Rooted Trees
• A New Approach to Incremental Cycle Detection and Related Problems
• An Improved Algorithm for Incremental Cycle Detection and Topological Ordering in Sparse Graphs
• Dynamic trees in practice
• Minimization of symbolic automata
• On the State Minimization of Nondeterministic Finite Automata
• Derivatives of Regular Expressions
• Model checking of safety properties

This page was built for publication: Incremental dead state detection in logarithmic time