可表示置换群的2-可表示性

摘要

随着计算机应用技术的发展,在形式语言的并行计算复杂度的研究中逐渐引入了布尔函数不变群的概念,置换群的可表示理论也逐渐引起人们注意.人们在研究可表示理论的过程中,解决了一些问题,但发现了更多的新问题,例如置换群的可表示性与2-可表示性并不等价.该文就是从这一个新问题入手,最终得到一个基本的事实.提出了置换群的可表示性与2-可表示性并不等价的问题.通过对D的进一步的思考,作者发现如果把D放在S<,5>中,那么它却是2-可表示的.最后,作者推广D的特殊性到一般情况,得到该文的主要结论.得到此结论的主要难点在于构造2-值布尔函数.分了二种情况,用了二种构造方法加以讨论,最终达到了目的.

目录

英文文摘

前言

§1主要定义和基本事实

§2问题的提出

§3定理2.3的证明

参考文献

致谢