Fine-grained complexity of safety verification
DOI10.1007/s10817-020-09572-xzbMath1468.68121OpenAlexW2787008790MaRDI QIDQ5919003
Prakash Saivasan, Roland Meyer, Peter Chini
Publication date: 2 November 2020
Published in: Journal of Automated Reasoning (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10817-020-09572-x
Analysis of algorithms (68W40) Specification and verification (program logics, model checking, etc.) (68Q60) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Parameterized complexity, tractability and kernelization (68Q27)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Constrained multilinear detection and generalized graph motifs
- Fundamentals of parameterized complexity
- Infeasibility of instance compression and succinct PCPs for NP
- Some consequences of non-uniform conditions on uniform classes
- On problems without polynomial kernels
- Model-checking linear-time properties of parametrized asynchronous shared-memory pushdown systems
- A multi-parameter analysis of hard problems on deterministic finite automata
- On atomicity in presence of non-atomic writes
- Problems on Finite Automata and the Exponential Time Hypothesis
- Parameterised Pushdown Systems with Non-Atomic Writes
- Parameterized Verification of Asynchronous Shared-Memory Systems
- On the Reachability Analysis of Acyclic Networks of Pushdown Systems
- Context-Bounded Analysis for Concurrent Programs with Dynamic Creation of Threads
- The Complexity of Predicting Atomicity Violations
- The Complexity of Satisfiability of Small Depth Circuits
- Testing Shared Memories
- On Problems as Hard as CNF-SAT
- Kernelization Lower Bounds by Cross-Composition
- Reducibility among Combinatorial Problems
- On the Complexity of Bounded Context Switching.
- Parameterized Algorithms
- Tools and Algorithms for the Construction and Analysis of Systems
- Graph-Theoretic Concepts in Computer Science
- Model checking parameterized asynchronous shared-memory systems
- Fine-grained complexity of safety verification
- On the complexity of \(k\)-SAT
