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

3, 7, 13, 14, 15, 18

Offset: 1

Author

Alexander Malkis, Aug 08 2017

Keywords

• nonn
• hard
• more

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.

Crossrefs

A008585(n) <= a(n) for all n >= 1.

Formula

a(n) >= 3*n for all n >= 1.

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

Extensions

Name edited by Michel Marcus, Jan 02 2020