論理関数のグラフ表現の性質と双対比への応用

逻辑函数的图形表示的性质及其对偶对比的应用

基本信息

批准号：
09780267
负责人：
武永康彦
金额：
$ 1.09万
依托单位：
The University of Electro-Communications
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1997
资助国家：
日本
起止时间：
1997 至 1998
项目状态：
已结题

项目摘要

本研究では、二分決定木や分岐プログラムなど理論上実際上重要な、グラフによる論理関数の表現法について、研究を行なってきた。本年度の研究成果の詳細は以下の通りである。1. 分岐プログラムの性質と表現能力に関する研究分岐プログラムの一種で、効率的な論理関数の表現法として知られる二分決定グラフについて、論理関数の正の例および負の例からの学習可能性について研究を行なった。具体的には、すべての例を満たす最小サイズの二分決定グラフを求める問題が、関数をしきい値関数に制限した場合でもNP困難であることを示した。2. 論理関数双対化等への応用前年度に提案した、論理関数を二分木表現の1つの経路が1つの素項に対応するような正論理関数のクラスについて、決定木の変数順序を固定した場合(ordered tree-shellable関数)、固定しない場合(tree-shellable関数)にわけて、さらに研究を進めた。(Ordered)tree-shellableであることがわかれば、効率良い双対化等、その特長の活用が可能だが、それにはこれらのクラスに属するかどうかの判定が必要となる。Quadratic関数(積和形表現の各積項のリテラル数が2個)に対しては多項式時間で判定可能であるが、一般の場合についても、リテラル数が2個の積項だけを取り出した関数が(ordered)tree-shellableであることが、必要条件となることを示した。また、前年度のプログラムを改良し、変数の置換によって等価となる関数を1個とみなした場合も含め、6変数までの関数に対して、これらの性質を持つ関数の個数を具体的に求めた。

在这项研究中，我们研究了使用图表（例如二进制决策树和分支程序）表达逻辑功能的理论和实际重要方法。今年研究结果的详细信息如下。 1。对分支程序的性质和表达能力的研究一种分支程序的类型，并研究了从逻辑函数的正面和负面示例的学习可能性上的二分法决策图，被称为有效表达逻辑功能的方法。具体而言，我们已经表明，找到满足所有示例的最小尺寸的二进制决策图，即使函数仅限于阈值函数也很难NP。 2。应用于逻辑函数偶性等。我们通过除去上一年提出的逻辑功能，例如一类正逻辑函数进行了进一步的研究，其中二进制树表达式中的一个路径与单个项相对应，而决策树的变量顺序是固定的（固定的树状函数）以及固定的（树状的功能）（树状函数）。如果已知它是（有序的）树壳，则可以使用其功能，例如有效的双重化，但是有必要确定它是否属于这些类别。尽管可以按多项式时间确定二次函数（产品总和中每个产品术语的文字数为2），但在一般情况下，已经显示出仅检索具有两个文字的产品项的函数（有序）是树状的。此外，这些属性的功能数量是针对多达六个变量的专门确定的，包括何时改善了上一年的程序，并且将变量替换为等效的函数被认为是一个函数。