Quasi-linearizability is undecidable

DOI10.1007/978-3-319-26529-2_20MaRDI QIDQ3459426zbMATH OpenOpenAlexFDO

Authors Chao Wang, Yi Lv, Gaoang Liu, Peng Wu

Publication date 8 January 2016

Published in Programming Languages and Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-26529-2_20

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• TSO-to-TSO linearizability is undecidable
• TSO-to-TSO linearizability is undecidable
• Bounded TSO-to-SC linearizability is decidable
• Decidability and complexity for quiescent consistency and its variations
• Decidability and complexity for quiescent consistency

Cited in

(4)

• TSO-to-TSO linearizability is undecidable
• Bounded TSO-to-SC linearizability is decidable
• Decomposable relaxation for concurrent data structures
• TSO-to-TSO linearizability is undecidable

This page was built for publication: Quasi-linearizability is undecidable

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