๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A Lower Bound on Wait-Free Counting

โœ Scribed by Shlomo Moran; Gadi Taubenfeld

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
209 KB
Volume
24
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

A Lower Bound on Blocking Semiovals
A Lower Bound on Blocking Semiovals
โœ Jeremy M. Dover ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 87 KB

A semioval in a projective plane is a set S of points such that for every point P โˆˆ S, there exists a unique line of such that โˆฉ S = {P}. In other words, at every point of S, there exists a unique tangent line. A blocking set in is a set B of points such that every line of contains at least one poin

Lower bounds on size and independence in
Lower bounds on size and independence inK4-free graphs
โœ Fraughnaugh, Kathryn L.; Locke, Stephen C. ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 131 KB ๐Ÿ‘ 1 views

We investigate lower bounds on the size of K 4 -free graphs. For several ranges of independence relative to order and for graphs with maximum degree 3 and 4, we find sharp lower bounds. We also evaluate Ramsey-type numbers over the classes of graphs with maximum degree 3 and with maximum degree 4.

A lower bound on the size of ฮต-free NFA
A lower bound on the size of ฮต-free NFA corresponding to a regular expression
โœ Yuri Lifshits ๐Ÿ“‚ Article ๐Ÿ“… 2003 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 110 KB

Hromkovic et al. showed how to transform a regular expression of size n into an ฮต-free nondeterministic finite automaton (which defines the same language as the expression) with O(n) states and O(n log 2 (n)) transitions. They also established a lower bound (n log(n)) on the number of transitions. W