自己双対正論理関数の分解について

概要

論文の詳細を見る
分散システムの相互排除に用いられるコテリとは,集合族Cで,どのS,S′∈Cも比較不能かつS∩S′≠∅を満たすものをいう.集合族Cに対し,正論理関数fcを次のように定義する.ベクトルxがCのある部分集合Sの特性ベクトル以上であるときfc(x)=1,そうでなければfc(x)=0.このとき,C:コテリ⟺fc:劣双対,C:優コテリ⟺fc:自己双対,という関係が知られている.本論文では,大きな優コテリを小さな優コテリからどのように構成するかを調べるため,自己双対正関数をより小さな自己双対正関数へ分解する方法を調べる.この目的には,劣双対関数fをいくつかの自己双対正関数の積f=f_1f_2…f_kに分解することが基本ステップになる.そこで,この分解を可能にする一般的な条件とともに,2個の自己双対正関数への分解f=f_1f_2の必要十分条件を与える.さらに,正準分解の概念を導入し,極小正準分解を求めるアルゴリズム,および(極小性は保証できないが)簡単で多項式時間で動作する一つの分解アルゴリズムを提案する.
1994-05-13