On the Complexity of Bounded Context Switching.

DOI10.4230/LIPIcs.ESA.2017.27zbMath1442.68073arXiv1609.09728OpenAlexW2964098997MaRDI QIDQ5111714

Peter Chini, Roland Meyer, Andreas Krebs, Jonathan Kolberg, Prakash Saivasan

Publication date: 27 May 2020

Full work available at URL: https://arxiv.org/abs/1609.09728

zbMATH Keywords

fixed-parameter tractabilityexponential time hypothesissafety verificationshared memory concurrencybounded context switching

Mathematics Subject Classification ID

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) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (5)

Stateless model checking under a reads-value-from equivalence ⋮ Reachability of scope-bounded multistack pushdown systems ⋮ Bounded Context Switching for Valence Systems ⋮ Fine-grained complexity of safety verification ⋮ On the Complexity of Bounded Context Switching.

Uses Software

• DiVinE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Constrained multilinear detection and generalized graph motifs
• Even faster integer multiplication
• Fundamentals of parameterized complexity
• Infeasibility of instance compression and succinct PCPs for NP
• Some consequences of non-uniform conditions on uniform classes
• Strong computational lower bounds via parameterized complexity
• 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
• Parametrized complexity theory.
• Problems on Finite Automata and the Exponential Time Hypothesis
• Kernelization – Preprocessing with a Guarantee
• Global Model Checking of Ordered Multi-Pushdown Systems
• Parameterised Pushdown Systems with Non-Atomic Writes
• Reachability of Multistack Pushdown Systems with Scope-Bounded Matching Relations
• Analyzing Asynchronous Programs with Preemption
• Context-Bounded Analysis For Concurrent Programs With Dynamic Creation of Threads
• Reducing Concurrent Analysis Under a Context Bound to Sequential Analysis
• On the Reachability Analysis of Acyclic Networks of Pushdown Systems
• Fourier meets M\"{o}bius: fast subset convolution
• Faster Integer Multiplication
• The Complexity of Predicting Atomicity Violations
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• The Complexity of Satisfiability of Small Depth Circuits
• Testing Shared Memories
• On Problems as Hard as CNF-SAT
• On the Complexity of Bounded Context Switching.
• Complexity of pattern-based verification for multithreaded programs
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• 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
• On the complexity of \(k\)-SAT

This page was built for publication: On the Complexity of Bounded Context Switching.