Size-estimation framework with applications to transitive closure and reachability
From MaRDI portal
Recommendations
- Verified over-approximation of the diameter of propositionally factored transition systems
- Reachability logic: an efficient fragment of transitive closure logic
- Size-change termination and transition invariants
- On the power of deterministic transitive closures
- An intuitionistic analysis of size-change termination
- Computing transitive closure on systolic arrays of fixed size
- Bounds on the automata size for Presburger arithmetic
- Inductive termination proofs with transition invariants and their relationship to the size-change abstraction
- Abstract derivation of transitive closure algorithms
- Size-change termination and satisfiability for linear-time temporal logics
Cites work
- scientific article; zbMATH DE number 4018089 (Why is no real title available?)
- scientific article; zbMATH DE number 5542185 (Why is no real title available?)
- scientific article; zbMATH DE number 4060392 (Why is no real title available?)
- scientific article; zbMATH DE number 3626409 (Why is no real title available?)
- scientific article; zbMATH DE number 3249395 (Why is no real title available?)
- scientific article; zbMATH DE number 3303654 (Why is no real title available?)
- scientific article; zbMATH DE number 3349081 (Why is no real title available?)
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- High-Probability Parallel Transitive-Closure Algorithms
- Matrix multiplication via arithmetic progressions
- On optimizing multiplications of sparse matrices
- Parallel Depth-First Search in General Directed Graphs
- Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
Cited in
(31)- Distributed agreement in dynamic peer-to-peer networks
- In-network estimation of frequency moments
- scientific article; zbMATH DE number 1563190 (Why is no real title available?)
- Analysis and application of adaptive sampling
- Generalized substring selectivity estimation
- Optimal sampling from sliding windows
- Binary vectors for fast distance and similarity estimation
- A fully polynomial parameterized algorithm for counting the number of reachable vertices in a digraph
- scientific article; zbMATH DE number 7278047 (Why is no real title available?)
- Spatially-decaying aggregation over a network
- Private multiparty sampling and approximation of vector combinations
- A fast algorithm for source-wise round-trip spanners
- On the estimate of the size of a directed graph
- How to catch \(L_2\)-heavy-hitters on sliding windows
- A note on the complexity of computing the number of reachable vertices in a digraph
- Algorithms and estimators for summarization of unaggregated data streams
- A unified scheme for generalizing cardinality estimators to sum aggregation
- Range minima queries with respect to a random permutation, and approximate range counting
- The overlay of minimization diagrams in a randomized incremental construction
- d-k-min-wise independent family of hash functions
- Near-optimal clustering in the \(k\)-machine model
- Computing rarity on uncertain data
- Communication lower bounds and optimal algorithms for numerical linear algebra
- On approximate range counting and depth
- Efficient distributed approximation algorithms via probabilistic tree embeddings
- Simple multi-party set reconciliation
- Towards robust and efficient computation in dynamic peer-to-peer networks
- Exponential time improvement for min-wise based algorithms
- Efficient processing of substring match queries with inverted variable-length gram indexes
- A fully dynamic algorithm for maintaining the transitive closure
- On the Complexity of Universal Leader Election
This page was built for publication: Size-estimation framework with applications to transitive closure and reachability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1384531)
