OFFSET
1,1
COMMENTS
Here, a binary n-threaded program is a multithreaded program with n threads, two local states per thread, and 2 shared states.
Conjecture: a(n) = 3*n for all n >= 5.
LINKS
Alexander Malkis, Reachability in Multithreaded Programs Is Polynomial in the Number of Threads (Version with Proofs), Technical University of Munich (Germany, 2019).
Alexander Malkis and Steffen Borgwardt, Reachability in Binary Multithreaded Programs Is Polynomial, ICDCS'17, IEEE, 2017, pages 2083-2088.
FORMULA
a(n) >= 3*n for all n >= 1.
a(n) <= n^{2^{13}} for all n >= 2.
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
Alexander Malkis, Aug 08 2017
EXTENSIONS
Name edited by Michel Marcus, Jan 02 2020
STATUS
approved