login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 0
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: 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 3 23:14 EDT 2020. Contains 335419 sequences. (Running on oeis4.)