MONOTONE SEPARATION OF LOGARITHMIC SPACE FROM LOGARITHMIC DEPTH

Authors
GRIGNI M SIPSER M
Citation
M. Grigni et M. Sipser, MONOTONE SEPARATION OF LOGARITHMIC SPACE FROM LOGARITHMIC DEPTH, Journal of computer and system sciences, 50(3), 1995, pp. 433-437
Citations number
15
Categorie Soggetti
System Science","Computer Science Hardware & Architecture","Computer Science Theory & Methods
Journal title
Journal of computer and system sciences → ACNP
ISSN journal
00220000
Volume
50
Issue
3
Year of publication
1995
Pages
433 - 437
Database
ISI
SICI code
0022-0000(1995)50:3<433:MSOLSF>2.0.ZU;2-1
Abstract
We show that the monotone analogue of logspace computation is more pow erful than monotone log-depth circuits: monotone bounded fanin circuit s for a certain function in monotone logspace require depth Omega(lg(2 )n). (C) 1995 Academic Press, Inc.