start-ver=1.4
cd-journal=joma
no-vol=J100-D
cd-vols=
no-issue=6
article-no=
start-page=616
end-page=626
dt-received=
dt-revised=
dt-accepted=
dt-pub-year=2017
dt-pub=20170601
dt-online=
en-article=
kn-article=
en-subject=
kn-subject=
en-title=An Efficient Algorithm to Determine Equivalence of Pipelined Dependency Graphs for Their Simplification
kn-title=パイプライン化依存性グラフを簡単化するための効率的な等価性判定アルゴリズム
en-subtitle=
kn-subtitle=
en-abstract=
kn-abstract=　依存性グラフに基づいた非同期式パイプライン制御回路の設計方法が提案されている．この設計法の最終段階においては，依存性グラフと縮小した依存性グラフの等価性を何度も繰返し判定することにより，簡単化した依存性グラフが得られる．しかし，この判定には多数の状態をもつオートマトンを扱うため，その計算量は極めて大きい．本論文では，この等価性判定のための新たな効率的なアルゴリズムを提案する．まず，基本操作の実行順序の半順序をコンパクトに表現するために，基本操作直結因果関係グラフ O˙ を定義する．次に，分
岐系列ごとに O˙ の高々二つの部分グラフが一致するとき，かつそのときに限り，二つの依存性グラフが等価であることを証明する．更に，等価性の判定に必要な分岐系列のサイズと数が有限であることを証明する．最後に，上述の原理を用いたアルゴリズムの計算量が従来法に比べて大幅に小さいことを示す．
en-copyright=
kn-copyright=

en-aut-name=KagotaniHiroto
en-aut-sei=Kagotani
en-aut-mei=Hiroto
kn-aut-name=籠谷裕人
kn-aut-sei=籠谷
kn-aut-mei=裕人
aut-affil-num=1
ORCID=

en-aut-name=SugiyamaYuji
en-aut-sei=Sugiyama
en-aut-mei=Yuji
kn-aut-name=杉山裕二
kn-aut-sei=杉山
kn-aut-mei=裕二
aut-affil-num=2
ORCID=

en-aut-name=OkamotoTakuji
en-aut-sei=Okamoto
en-aut-mei=Takuji
kn-aut-name=岡本卓爾
kn-aut-sei=岡本
kn-aut-mei=卓爾
aut-affil-num=3
ORCID=

affil-num=1
en-affil=Graduate School of Natural Science and Technology
kn-affil=岡山大学大学院自然科学研究科

affil-num=2
en-affil=Graduate School of Natural Science and Technology
kn-affil=岡山大学大学院自然科学研究科

affil-num=3
en-affil=
kn-affil=
en-keyword=非同期式制御回路
kn-keyword=非同期式制御回路
en-keyword=パイプライン
kn-keyword=パイプライン
en-keyword=簡単化
kn-keyword=簡単化
en-keyword=因果関係
kn-keyword=因果関係
END

start-ver=1.4
cd-journal=joma
no-vol=
cd-vols=
no-issue=
article-no=
start-page=280
end-page=285
dt-received=
dt-revised=
dt-accepted=
dt-pub-year=1994
dt-pub=19941115
dt-online=
en-article=
kn-article=
en-subject=
kn-subject=
en-title=
kn-title=Minimum test sets for locally exhaustive testing of combinational circuits with five outputs
en-subtitle=
kn-subtitle=
en-abstract=
kn-abstract=<p>In this paper, features of dependence matrices of combinational circuits with five outputs are discussed, and it is shown that a minimum test set for locally exhaustive testing of such circuits always has 2 w test patterns, where w is the maximum number of inputs on which any output depends</p>

en-copyright=
kn-copyright=

en-aut-name=YokohiraTokumi
en-aut-sei=Yokohira
en-aut-mei=Tokumi
kn-aut-name=
kn-aut-sei=
kn-aut-mei=
aut-affil-num=1
ORCID=

en-aut-name=ShimizuToshimi
en-aut-sei=Shimizu
en-aut-mei=Toshimi
kn-aut-name=
kn-aut-sei=
kn-aut-mei=
aut-affil-num=2
ORCID=

en-aut-name=MichinishiHiroyuki
en-aut-sei=Michinishi
en-aut-mei=Hiroyuki
kn-aut-name=
kn-aut-sei=
kn-aut-mei=
aut-affil-num=3
ORCID=

en-aut-name=SugiyamaYuji
en-aut-sei=Sugiyama
en-aut-mei=Yuji
kn-aut-name=
kn-aut-sei=
kn-aut-mei=
aut-affil-num=4
ORCID=

en-aut-name=OkamotoTakuji
en-aut-sei=Okamoto
en-aut-mei=Takuji
kn-aut-name=
kn-aut-sei=
kn-aut-mei=
aut-affil-num=5
ORCID=

affil-num=1
en-affil=
kn-affil=Okayama University

affil-num=2
en-affil=
kn-affil=Okayama University

affil-num=3
en-affil=
kn-affil=Okayama University

affil-num=4
en-affil=
kn-affil=Okayama University

affil-num=5
en-affil=
kn-affil=Okayama University
en-keyword=combinational circuits
kn-keyword=combinational circuits
en-keyword=logic testing
kn-keyword=logic testing
en-keyword=matrix algebra
kn-keyword=matrix algebra
END