Showing 2023Show all
2 papers · 1 filter
cs.PL2023
Linearizability Analysis of the Contention-Friendly Binary Search Tree
Uri Abraham, Avi Hayoun
We present a formal framework for proving the correctness of set implementations backed by binary-search-tree (BST) and linked lists, which are often difficult to prove correct usi…
math.LO2023
On the ABK Conjecture, alpha-well Quasi Orders and Dress-Schiffels product
Uri Abraham, Robert Bonnet, Mirna Džamonja +1
The following is a 2008 conjecture of Abraham, Bonnet and Kubiś: [ABK Conjecture] Every well quasi order (wqo) is a countable union of better quasi orders (bqo). We obtain a partia…