Decidability and complexity for quiescent consistency and its variations
From MaRDI portal
Publication:1680503
DOI10.1016/j.ic.2017.09.012zbMath1380.68294MaRDI QIDQ1680503
Robert M. Hierons, Brijesh Dongol
Publication date: 16 November 2017
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2017.09.012
68Q25: Analysis of algorithms and problem complexity
68Q60: Specification and verification (program logics, model checking, etc.)
68Q85: Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Abstraction for concurrent objects
- On reducing linearizability to state reachability
- Model-checking of correctness conditions for concurrent objects
- Tractable Refinement Checking for Concurrent Objects
- Quantitative relaxation of concurrent data structures
- The complexity of equivalence problems for commutative grammars
- How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs
- Counting networks
- Decidability and Complexity for Quiescent Consistency
- Characterizations of the decidability of some problems for regular trace languages
- Parameterised Linearisability
- Between Linearizability and Quiescent Consistency
- Verifying Concurrent Programs against Sequential Specifications
- On verifying causal consistency
- The complexity of satisfiability problems
- A variant of a recursively unsolvable problem