The On-Line Encyclopedia of Integer Sequences (OEIS)

Revision History for A290642

(Bold, blue-underlined text is an addition; faded, red-underlined text is a ~~deletion~~.)
Showing entries 1-10 | older changes

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.
(history; published version)

#46 by Peter Luschny at Tue Mar 05 07:02:19 EST 2024

STATUS

reviewed

approved

#45 by Michel Marcus at Tue Mar 05 05:03:35 EST 2024

STATUS

proposed

reviewed

#44 by Joerg Arndt at Tue Mar 05 03:43:06 EST 2024

STATUS

editing

proposed

#43 by Alexander Malkis at Thu Feb 29 14:15:54 EST 2024

LINKS

Alexander Malkis, <a href="httpshttp://www.secwwwbroy.in.tum.de/~malkis/Malkis_-ReachabilityInMultithreadedProgramsIsPolynomialInTheNumberOfThreads__Reachability_in_Multithreaded_Programs_Is_Polynomial_in_the_Number_of_Threads_techrep.pdf">Reachability in Multithreaded Programs Is Polynomial in the Number of Threads (Version with Proofs)</a>, Technical University of Munich (Germany, 2019).

STATUS

approved

editing

Discussion

Thu Feb 29

14:18

Alexander Malkis: My old paper location https://www.sec.in.tum.de/~malkis/Malkis-ReachabilityInMultithreadedProgramsIsPolynomialInTheNumberOfThreads_techrep.pdf is going to expire soon according to the sysadmin. I corrected somne typos and uploaded the paper to a newer location (which is also going to expire but probably much later).

#42 by N. J. A. Sloane at Thu Jan 02 20:40:11 EST 2020

STATUS

proposed

approved

#41 by Michel Marcus at Thu Jan 02 16:47:28 EST 2020

STATUS

editing

proposed

Discussion

Thu Jan 02

18:15

Michael De Vlieger: For me, yes.

#40 by Michel Marcus at Thu Jan 02 16:47:20 EST 2020

NAME

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

Discussion

Thu Jan 02

16:47

Michel Marcus: ok ?

#39 by Michel Marcus at Thu Jan 02 16:46:54 EST 2020

NAME

The initial terms for diamaxa(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.

COMMENTS

Here, a binary n-threaded program is a multithreaded program with n threads, two local states per thread, and 2 shared states.

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

FORMULA

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

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

CROSSREFS

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

EXTENSIONS

Name edited by Michel Marcus, Jan 02 2020

#38 by Michel Marcus at Thu Jan 02 16:44:38 EST 2020

KEYWORD

nonn,hard,more,nonn,changed

STATUS

proposed

editing

Discussion

Thu Jan 02

16:45

Michel Marcus: use a(n) in formula and xrefs ?

16:45

Michel Marcus: and comments ?

#37 by Michael De Vlieger at Thu Jan 02 16:33:09 EST 2020

STATUS

editing

proposed