𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A lower bound for the nondeterministic space complexity of context-free recognition

✍ Scribed by Helmut Alt; Viliam Geffert; Kurt Mehlhorn

Publisher
Elsevier Science
Year
1992
Tongue
English
Weight
241 KB
Volume
42
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Lower Bounds for the Complexity of Funct
Lower Bounds for the Complexity of Functions in a Realistic RAM Model
✍ Nader H. Bshouty πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 127 KB

This paper develops a new technique that finds almost tight lower bounds for the complexity of programs that compute or approximate functions in a realistic RAM model. The nonuniform realistic RAM model is a model that uses the arithmetic Γ„ 4 operations q, y, = , the standard bit operation Shift, Ro

On a Lower-Bound for the Absolute Value
On a Lower-Bound for the Absolute Value of a Polynomial of Several Complex Variables
✍ B. Paneah πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 268 KB

For an arbitrary polynomial \(P\left(z_{1}, z_{2}, \ldots, z_{n}\right)\) in complex space \(\mathbb{C}^{n}\) we describe a set of nonnegative multi-indices \(\alpha=\left(\alpha_{1}, \alpha_{2}, \ldots, \alpha_{n}\right)\) such that for any \(n\)-tuple \(\delta=\left(\delta_{1}, \delta_{2}, \ldots,