A290642 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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

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 2083-2088.

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: A238476 A118889 A077149 * 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