𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Tight Lower Bounds on the Size of Sweeping Automata

✍ Scribed by Hing Leung

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
124 KB
Volume
63
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On the minimum size of tight hypergraphs
On the minimum size of tight hypergraphs
✍ Jorge L. Arocha; Javier Bracho; Victor Neumann-Lara πŸ“‚ Article πŸ“… 1992 πŸ› John Wiley and Sons 🌐 English βš– 333 KB

## Abstract A __k__‐graph, __H__ = (__V, E__), is __tight__ if for every surjective mapping __f__: __V__ β†’ {1,….k} there exists an edge Ξ± Ο΅ __E__ sicj tjat __f__|~Ξ±~ is injective. Clearly, 2‐graphs are tight if and only if they are connected. Bounds for the minimum number Ο• of edges in a tight __k_

New lower bounds for the size of edge ch
New lower bounds for the size of edge chromatic critical graphs
✍ Yue Zhao πŸ“‚ Article πŸ“… 2004 πŸ› John Wiley and Sons 🌐 English βš– 108 KB πŸ‘ 1 views

## Abstract In this paper, by applying the discharging method, we obtain new lower bounds for the size of edge chromatic critical graphs for small maximum degree Ξ”. Β© 2004 Wiley Periodicals, Inc. J Graph Theory 46: 81–92, 2004

Tight bounds on the chromatic sum of a c
Tight bounds on the chromatic sum of a connected graph
✍ Carsten Thomassen; Paul ErdΓΆs; Yousef Alavi; Paresh J. Malde; Allen J. Schwenk πŸ“‚ Article πŸ“… 1989 πŸ› John Wiley and Sons 🌐 English βš– 236 KB πŸ‘ 1 views
Lower Bounds on the Depth of Monotone Ar
Lower Bounds on the Depth of Monotone Arithmetic Computations
✍ Don Coppersmith; Baruch Schieber πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 128 KB

dedicated to zvi galil's 50th birthday Consider an arithmetic expression of length n involving only the operations [+, \_] and non-negative constants. We prove lower bounds on the depth of any binary computation tree over the same sets of operations and constants that computes such an expression. We