

A290642


The initial terms for diamax(n), which is the maximum diameter for an nthreaded binary program. In other words, diamax(n) is the maximal finite distance in the transition graph of an nthreaded binary program. Here, a binary nthreaded program is a multithreaded program with n threads, two local states per thread, and 2 shared states.


0




OFFSET

1,1


COMMENTS

Conjecture: diamax(n) = 3*n for all n >= 5.


LINKS

Table of n, a(n) for n=1..6.
Alexander Malkis and Steffen Borgwardt, Reachability in Binary Multithreaded Programs Is Polynomial, ICDCS'17, IEEE, 2017, pages 20832088.


FORMULA

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


CROSSREFS

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


KEYWORD

hard,more,nonn


AUTHOR

Alexander Malkis, Aug 08 2017


STATUS

approved



