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

A lower bound technique for the size of nondeterministic finite automata

โœ Scribed by Ian Glaister; Jeffrey Shallit

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
209 KB
Volume
59
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

An Exponential Lower Bound for the Size
An Exponential Lower Bound for the Size of Monotone Real Circuits
โœ Armin Haken; Stephen A. Cook ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 118 KB

We prove a lower bound, exponential in the eighth root of the input length, on the size of monotone arithmetic circuits that solve an NP problem related to clique detection. The result is more general than the famous lower bound of Razborov and Andreev, because the gates of the circuit are allowed t

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

A superlinear lower bound for the size o
A superlinear lower bound for the size of a critical set in a latin square
โœ Nicholas J. Cavenagh ๐Ÿ“‚ Article ๐Ÿ“… 2007 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 157 KB ๐Ÿ‘ 1 views

## Abstract A critical set is a partial latin square that has a unique completion to a latin square, and is minimal with respect to this property. Let __scs__(__n__) denote the smallest possible size of a critical set in a latin square of order __n__. We show that for all __n__, $scs(n)\geq n\lfloo