講演抄録/キーワード |
講演名 |
2006-12-04 17:05
Linear-Size Log-Depth Negation-Limited Inverter for k-tonic 0/1 Sequences ○Hiroki Morizumi(Kyoto Univ.)・Jun Tarui(Univ. of Electro-Comm.) |
抄録 |
(和) |
0/1列$x_1, \ldots, x_n$は,$1 \leq i \leq n-1$に対して$x_i \neq x_{i+1}$である$i$の数がたかだか$k$であるとき$k$トニックであるという.本研究では,サイズ$O((\log k) \cdot n)$,深さ$O((\log k) \cdot \log \log n + \log n)$,含まれるNOT素子の数$\log_2 n + O(\log\log n)$である$k$トニック列の0/1を反転する回路の構成法を与える.我々の構成法はすべての点において佐藤らによる構成法(サイズ$O(kn)$,深さ$O(k\log^{2}n)$,NOT素子の数$O(k\log n)$)を改善している.$k = O(1)$であるとき,佐藤らによる構成法は$O(\log^{2}n)$の深さを必要としたが,我々の構成法はNOT素子の数$O(\log n)$で線形サイズ,対数深さを実現している.BelasらはNOT素子を$\lceil \log_2(n+1) \rceil$使用したサイズ$O(n\log n)$,深さ$O(\log n)$のすべての列に対するインバータの構成法を与えた.$k=n^{o(1)}$であるとき,我々の構成法は同等の深さと$O(\log\log n)$のNOT素子の増加のみでそのサイズを$o(n\log n)$に減少させる.$k$トニック列に対するインバータの構成における我々の考察はk$トニック列をソートする回路に関しても佐藤らによるものを改善する. |
(英) |
A binary sequence $x_1, \ldots, x_n$ is called $k$-tonic if for $1 \leq i \leq n-1$ the number of $i$'s such that $x_i \neq x_{i+1}$ is at most $k$. In this paper, we give the construction of a circuit inverting $k$-tonic sequences, which has size $O((\log k) \cdot n)$ depth $O((\log k) \cdot \log \log n + \log n)$ and contains $\log_2 n + O(\log\log n)$ NOT gates. Our construction improves all parameters of the construction by Sato, Amano and Maruoka, whose size is $O(kn)$ and depth is $O(k\log^{2}n)$ using $O(k\log n)$ NOT gates. If $k = O(1)$, the previous construction needs $O(\log^{2}n)$ depth, but our inverter has linear size and log depth using $O(\log n)$ NOT gates. Beals, Nishino and Tanaka have shown the construction of a size $O(n\log n)$ depth $O(\log n)$ inverter for all sequences with $\lceil \log_2(n+1) \rceil$ NOT gates. If $k=n^{o(1)}$, our construction reduces the size to $o(n\log n)$ with the same depth and only $O(\log\log n)$ increase of the number of NOT gates. Our idea on the construction of an inverter for $k$-tonic sequences also give an improvement for a circuit sorting $k$-tonic sequences from the construction by Sato, Amano and Maruoka. |
キーワード |
(和) |
回路計算量 / 否定数限定回路 / インバータ / ソータ / $k$トニック / / / |
(英) |
Circuit Complexity / Negation-Limited Circuit / Inverter / Sorter / $k$-tonic / / / |
文献情報 |
信学技報, vol. 106, no. 405, COMP2006-49, pp. 57-60, 2006年12月. |
資料番号 |
COMP2006-49 |
発行日 |
2006-11-27 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 |
PDFダウンロード |
|
研究会情報 |
研究会 |
COMP |
開催期間 |
2006-12-04 - 2006-12-04 |
開催地(和) |
名古屋大学 |
開催地(英) |
Nagoya University |
テーマ(和) |
|
テーマ(英) |
|
講演論文情報の詳細 |
申込み研究会 |
COMP |
会議コード |
2006-12-COMP |
本文の言語 |
英語 |
タイトル(和) |
|
サブタイトル(和) |
|
タイトル(英) |
Linear-Size Log-Depth Negation-Limited Inverter for k-tonic 0/1 Sequences |
サブタイトル(英) |
|
キーワード(1)(和/英) |
回路計算量 / Circuit Complexity |
キーワード(2)(和/英) |
否定数限定回路 / Negation-Limited Circuit |
キーワード(3)(和/英) |
インバータ / Inverter |
キーワード(4)(和/英) |
ソータ / Sorter |
キーワード(5)(和/英) |
$k$トニック / $k$-tonic |
キーワード(6)(和/英) |
/ |
キーワード(7)(和/英) |
/ |
キーワード(8)(和/英) |
/ |
第1著者 氏名(和/英/ヨミ) |
森住 大樹 / Hiroki Morizumi / モリズミ ヒロキ |
第1著者 所属(和/英) |
京都大学 (略称: 京大)
Kyoto University (略称: Kyoto Univ.) |
第2著者 氏名(和/英/ヨミ) |
垂井 淳 / Jun Tarui / タルイ ジュン |
第2著者 所属(和/英) |
電気通信大学 (略称: 電通大)
University of Electro-Communications (略称: Univ. of Electro-Comm.) |
第3著者 氏名(和/英/ヨミ) |
/ / |
第3著者 所属(和/英) |
(略称: )
(略称: ) |
第4著者 氏名(和/英/ヨミ) |
/ / |
第4著者 所属(和/英) |
(略称: )
(略称: ) |
第5著者 氏名(和/英/ヨミ) |
/ / |
第5著者 所属(和/英) |
(略称: )
(略称: ) |
第6著者 氏名(和/英/ヨミ) |
/ / |
第6著者 所属(和/英) |
(略称: )
(略称: ) |
第7著者 氏名(和/英/ヨミ) |
/ / |
第7著者 所属(和/英) |
(略称: )
(略称: ) |
第8著者 氏名(和/英/ヨミ) |
/ / |
第8著者 所属(和/英) |
(略称: )
(略称: ) |
第9著者 氏名(和/英/ヨミ) |
/ / |
第9著者 所属(和/英) |
(略称: )
(略称: ) |
第10著者 氏名(和/英/ヨミ) |
/ / |
第10著者 所属(和/英) |
(略称: )
(略称: ) |
第11著者 氏名(和/英/ヨミ) |
/ / |
第11著者 所属(和/英) |
(略称: )
(略称: ) |
第12著者 氏名(和/英/ヨミ) |
/ / |
第12著者 所属(和/英) |
(略称: )
(略称: ) |
第13著者 氏名(和/英/ヨミ) |
/ / |
第13著者 所属(和/英) |
(略称: )
(略称: ) |
第14著者 氏名(和/英/ヨミ) |
/ / |
第14著者 所属(和/英) |
(略称: )
(略称: ) |
第15著者 氏名(和/英/ヨミ) |
/ / |
第15著者 所属(和/英) |
(略称: )
(略称: ) |
第16著者 氏名(和/英/ヨミ) |
/ / |
第16著者 所属(和/英) |
(略称: )
(略称: ) |
第17著者 氏名(和/英/ヨミ) |
/ / |
第17著者 所属(和/英) |
(略称: )
(略称: ) |
第18著者 氏名(和/英/ヨミ) |
/ / |
第18著者 所属(和/英) |
(略称: )
(略称: ) |
第19著者 氏名(和/英/ヨミ) |
/ / |
第19著者 所属(和/英) |
(略称: )
(略称: ) |
第20著者 氏名(和/英/ヨミ) |
/ / |
第20著者 所属(和/英) |
(略称: )
(略称: ) |
講演者 |
第1著者 |
発表日時 |
2006-12-04 17:05:00 |
発表時間 |
30分 |
申込先研究会 |
COMP |
資料番号 |
COMP2006-49 |
巻番号(vol) |
vol.106 |
号番号(no) |
no.405 |
ページ範囲 |
pp.57-60 |
ページ数 |
4 |
発行日 |
2006-11-27 (COMP) |
|