Incremental dead state detection in logarithmic time

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

Authors: Caleb Stanford, Margus Veanes 

Publication date: 12 January 2024

Recommendations

• Incremental topological sort and cycle detection in \(\tilde O(m \sqrt n)\) expected total time
• A new approach to incremental cycle detection and related problems
• The incremental maintenance of a depth-first-search tree in directed acyclic graphs
• Faster Algorithms for Incremental Topological Ordering
• Incremental cycle detection, topological ordering, and strong component maintenance

zbMATH Keywords

online algorithmsgraph algorithmsSMTdead-state detection

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Derivatives of Regular Expressions
• Partial derivatives of regular expressions and finite automaton constructions
• A data structure for dynamic trees
• Efficiency of a Good But Not Linear Set Union Algorithm
• Three Partition Refinement Algorithms
• Variations on the Common Subexpression Problem
• A dynamic topological sort algorithm for directed acyclic graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Efficient E-Matching for SMT Solvers
• Title not available (Why is that?)
• Fast Decision Procedures Based on Congruence Closure
• Regular expressions: new results and open problems
• Maintaining information in fully dynamic trees with top trees
• Title not available (Why is that?)
• A new approach to incremental cycle detection and related problems
• Model checking of safety properties
• Succinctness of the complement and intersection of regular expressions
• On the State Minimization of Nondeterministic Finite Automata
• Randomized fully dynamic graph algorithms with polylogarithmic time per operation
• Incremental cycle detection, topological ordering, and strong component maintenance
• A Data Structure for Dynamically Maintaining Rooted Trees
• Dynamic trees in practice
• Minimization of symbolic automata
• Title not available (Why is that?)
• A decision procedure for regular membership and length constraints over unbounded strings
• Title not available (Why is that?)
• Erratum to ``Acyclic automata and small expressions using multi-tilde-bar operators [Theoret. Comput. Sci. 411 (38-39) (2010) 3423-3435]
• Improved Dynamic Reachability Algorithms for Directed Graphs
• Advanced automata minimization
• An O(n \text{log} n) implementation of the standard method for minimizing n-state finite automata
• Maintaining a topological order under edge insertions
• Symbolic solving of extended regular expression inequalities
• An SMT solver for regular expressions and linear arithmetic over string length
• Title not available (Why is that?)
• Minimisation of automata
• Title not available (Why is that?)
• Incremental topological sort and cycle detection in \(\tilde O(m \sqrt n)\) expected total time
• An Improved Algorithm for Incremental Cycle Detection and Topological Ordering in Sparse Graphs

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

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