Classification of minimal clones in multiple-valued logic and finite fields

多值逻辑和有限域中最小克隆的分类

• 批准号: 18540116
• 负责人: MACHIDA Hajime
• 金额: $ 2.48万
• 依托单位: Hitotsubashi University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2006
• 资助国家: 日本
• 起止时间: 2006 至 2007
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18540116/
• 关键词: multiple-valued logic; universal algebra; clone theory; minimal clone

For a set A, a clone on A is a set of multi-variable functions on A which contains all projections and is closed under composition The set of all clones on A forms a lattice which is called the clone lattice over A and is denoted by L_A. The structure of L_A is extremely complex and , up to now, largely unknown.The clone J_A of all projections is clearly the least element of the lattice L_A. A minimal element of the set L_A-J A is called a minimal clone. A minimal clone is generated by a single function, which is called a minimal function..In this research, we employed a new method of research by introducing the structure of a finite field GF(|A|) into the finite base set A and treating minimal functions over the set A as polynomials defined over GF(|A|). In this way we tried to grasp the properties of minimal functions as the properties of polynomials over a finite field. Starting from the result of B. Csakany who presented all minimal clones over a three-element set, we first expressed Csakany's minimal functions as polynomials over GF(3) and generalized some of them to polynomials over arbitrary finite field GF(k) where k is any prime power.More specifically, we considered the cases where minimal functions are (1) binary idempotent functions and (2) ternary majority functions. We obtained, among others, the complete characterization of binary linear minimal polynomials as well as binary minimal monomials. Furthermore, we have obtained many examples of polynomials generating minimal clones over GF(k) for any prime power k.

对于集合A，A上的克隆是A上包含所有投影且在复合下闭的多元函数的集合。A上的所有克隆的集合形成一个格，称为A上的克隆格，记为L_A。L_A的结构非常复杂，迄今为止还不清楚，所有投影的克隆J_A显然是格L_A的最小元素。集合L_A-JA的极小元素称为极小克隆。最小克隆由单个函数生成，称为最小函数。在这项研究中，我们采用了一种新的研究方法，通过引入有限域GF（|一|）到有限基集合A中，并将集合A上的极小函数视为GF上定义的多项式（|一|).通过这种方式，我们试图掌握极小函数的性质作为有限域上多项式的性质。从B的结果开始。Csakany提出了三元集上的所有极小克隆，我们首先将Csakany的极小函数表示为GF（3）上的多项式，并将其中的一些推广到任意有限域GF（k）上的多项式，其中k是任意的素幂，更具体地，我们考虑了极小函数是（1）二元幂等函数和（2）三元多数函数的情况。除其他外，我们得到了二元线性极小多项式以及二元极小单项式的完整特征。此外，我们已经得到了许多例子的多项式生成最小克隆GF（k）的任何素数幂k。

项目成果

Majority and other polynomials in minimal clones

最小克隆中的多数多项式和其他多项式

• 发表时间: 2008
• 期刊: Proc. 38th International Symposium on Multiple-Valued Logic(IEEE Computer Society) 38(印刷中)
• 作者: 畑上到;鈴木修司;S. Tezuka;S. Tezuka;K. Ohmori;K. Ohmori;S. Tezuka;S. Tezuka;畑上到;手塚集;手塚集;手塚 集;H. Machida;H. Machida
• 通讯作者: H. Machida

Some remarks on minimal clones(II)

关于最小克隆的一些注解（二）

• 发表时间: 2007
• 作者: Haddad;L.;Machida;H.;Rosenberg;I. G;H. Machida
• 通讯作者: H. Machida

On minimal clones and generating polynomials

关于最小克隆和生成多项式

• 发表时间: 2008
• 期刊: 京都大学数理解析研究所 講究録 (印刷中)
• 作者: 畑上到;鈴木修司;S. Tezuka;S. Tezuka;K. Ohmori;K. Ohmori;S. Tezuka;S. Tezuka;畑上到;手塚集;手塚集;手塚 集;H. Machida;H. Machida;H. Machida
• 通讯作者: H. Machida

Polynomials as generators of minimal clones

多项式作为最小克隆的生成器

• 发表时间: 2007
• 期刊: Proc. 37th International Symposium on Multiple-Valued Logic(IEEE Computer Society) 37(DVD)
• 作者: Machida;H;H. Machida;H. Machida;H. Machida
• 通讯作者: H. Machida

Polynomials as generators ofminimal clones

多项式作为最小克隆的生成器

• 期刊: Proc. 37th International Symposium on Multiple-Valued Logic (IEEE Computer Society) (印刷中)
• 作者: Machida;H.;Pinsker;M;H.Machida;L.Haddad;H.Machida;H.Machida;H.Machida;H.Machida
• 通讯作者: H.Machida