login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A290642 The initial terms for diamax(n), which is the maximum diameter for an n-threaded binary program. In other words, diamax(n) is the maximal finite distance in the transition graph of an n-threaded binary program. Here, a binary n-threaded program is a multithreaded program with n threads, two local states per thread, and 2 shared states. 0
3, 7, 13, 14, 15, 18 (list; graph; refs; listen; history; text; internal format)
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 2083-2088.

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

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 June 19 11:21 EDT 2019. Contains 324219 sequences. (Running on oeis4.)