Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Circuits and Context-Free Languages
| |
|
Circuits and Context-Free Languages
Pierre McKenzie6  , Klaus Reinhardt7 and V. Vinay8
| (6) |
Informatique et recherche opérationnelle, Université de Montréal, C.P. 6128, Succ. Centre-Ville, Montréal, Québec, H3C 3J7, Canada |
| (7) |
Wilhelm-Schickard Institut für Informatik, Universität Tübingen, Sand 13, D-72076 Tübingen, Germany |
| (8) |
Department of Computer Science and Automation, Indian Institute of Science, Bangalore, 560 012, India |
Abstract
Simpler proofs that DAuxPDA-TIME(polynomial) equals LOG(DCFL) and that SAC1 equals LOG(CFL) are given which avoid Sudborough's multi-head automata [Sud78]. The first characterization of LOGDCFL in
terms of polynomial proof-tree-size is obtained, using circuits built from the multiplex select gates of [FLR96]. The classes
L and NC1 are also characterized by such polynomial size circuits: “self-similar” logarithmic depth captures L, and bounded width captures
NC1.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|