

A290642


a(n) is the maximum diameter for an nthreaded binary program. In other words, a(n) is the maximal finite distance in the transition graph of an nthreaded binary program.


0




OFFSET

1,1


COMMENTS

Here, a binary nthreaded 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

Table of n, a(n) for n=1..6.
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 20832088.


FORMULA

a(n) >= 3*n for all n >= 1.
a(n) <= n^{2^{13}} for all n >= 2.


CROSSREFS

A008585(n) <= a(n) for all n >= 1.
Sequence in context: A118889 A077149 A064829 * A295009 A310251 A035496
Adjacent sequences: A290639 A290640 A290641 * A290643 A290644 A290645


KEYWORD

nonn,hard,more


AUTHOR

Alexander Malkis, Aug 08 2017


EXTENSIONS

Name edited by Michel Marcus, Jan 02 2020


STATUS

approved



