On Depth-Bounded Planar Circuits
Summary :
We study the depth of planar Boolean circuits. We show that planar Boolean circuits of depth D(n) are simulated by on-line Turing machines in space O(D(n)). From this relationship, it is shown that any planar circuit for computing integer multiplication requires linear depth. It is also shown that a planar analogue to the NC-hierarchy is properly separated.
- Publication
- IEICE TRANSACTIONS on Information Vol.E75-D No.1 pp.110-115
- Publication Date
- 1992/01/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on Theoretical Foundations of Computing)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Masao IKEKAWA, "On Depth-Bounded Planar Circuits" in IEICE TRANSACTIONS on Information,
vol. E75-D, no. 1, pp. 110-115, January 1992, doi: .
Abstract: We study the depth of planar Boolean circuits. We show that planar Boolean circuits of depth D(n) are simulated by on-line Turing machines in space O(D(n)). From this relationship, it is shown that any planar circuit for computing integer multiplication requires linear depth. It is also shown that a planar analogue to the NC-hierarchy is properly separated.
URL: https://global.ieice.org/en_transactions/information/10.1587/e75-d_1_110/_p
Copy
@ARTICLE{e75-d_1_110,
author={Masao IKEKAWA, },
journal={IEICE TRANSACTIONS on Information},
title={On Depth-Bounded Planar Circuits},
year={1992},
volume={E75-D},
number={1},
pages={110-115},
abstract={We study the depth of planar Boolean circuits. We show that planar Boolean circuits of depth D(n) are simulated by on-line Turing machines in space O(D(n)). From this relationship, it is shown that any planar circuit for computing integer multiplication requires linear depth. It is also shown that a planar analogue to the NC-hierarchy is properly separated.},
keywords={},
doi={},
ISSN={},
month={January},}
Copy
TY - JOUR
TI - On Depth-Bounded Planar Circuits
T2 - IEICE TRANSACTIONS on Information
SP - 110
EP - 115
AU - Masao IKEKAWA
PY - 1992
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E75-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 1992
AB - We study the depth of planar Boolean circuits. We show that planar Boolean circuits of depth D(n) are simulated by on-line Turing machines in space O(D(n)). From this relationship, it is shown that any planar circuit for computing integer multiplication requires linear depth. It is also shown that a planar analogue to the NC-hierarchy is properly separated.
ER -
English
