2. 您的位置
3. 首页
4. 学位论文
5. 极小不可满足公式的改名和同态的计算复杂性

极小不可满足公式的改名和同态的计算复杂性

来源 :南京大学 | 被引量 : 0次 | 上传用户：ahhshpl

【摘 要】

：

一个变元改名是一个关于变元的置换,一个文字改名是允许某些变元变换到它的补的变元改名,一个同态则是允许不同文字变换到同一文字的文字改名.该文研究了极小不可满足公式的

【作 者】

：

许道云 

【机 构】

：

南京大学

【出 处】

：

南京大学

【发表日期】

：

2002年期

【关键词】

：

变元改名 变元置换 图同构 数理逻辑 

下载到本地 , 更方便阅读

下载此文 赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

一个变元改名是一个关于变元的置换,一个文字改名是允许某些变元变换到它的补的变元改名,一个同态则是允许不同文字变换到同一文字的文字改名.该文研究了极小不可满足公式的改名和同态的存在性判定问题的计算复杂性. 我们证明了:(1)MU(1)内的公式(即使Horn公式)的变元改名问题等价于图同构问题.(3)MAX和MARG内的公式的变元改名问题等价于图同构问题.等

其他文献

基于技术变量数据的L1惩罚二元泊松模型与足球赛果预测

随着足球竞彩市场的快速发展，我们获取的数据也不再局限于比赛结果，同时还可获得每场比赛的球队技术变量数据，但对于较高维度的技术变量尤其是对进球有重要影响的技术变量与进球

学位

足球竞彩随机变量赛果预测二元泊松

网络地图信息系统的设计和实现

传统的GIS Java数据库解决方案,有的是用JDBC的客户端解决方案,这种方案的网络效率不理想,系统的解决机制的网络配置也不理想.为了解决这样的问题,该系统的数据库的解决方案

学位

GIS矢量地图TCP/IPJava解决方案矩阵算法

低年级合作学习的“土地改革运动”

合作学习是新课程倡导的三大学习方式之一。新课程的实施引导了中小学课堂生机勃勃的改革实践,教师已经有意识地把合作学习策略引入课堂,合作学习的“身影”时隐时现地展现在

期刊

合作学习新课程中小学课堂学习方式学习策略课堂教学合作机会改革实践意识声音教师

一种新的子分曲面生成算法的研究及其应用

该文首先介绍了几种常见的子分曲面生成技术和目前的研究现状,并深入地分析了这几种子分方案的优缺点.然后,我们提出了一种在三角形网格拓扑结构上的基于法向量控制的子分曲

学位

计算机图形学子分曲面法向量控制自适应子分子分曲面生成技术

复杂系统可靠性与贮存可靠性综合评估

本文旨在建立复杂系统可靠性及贮存可靠性的综合评估方法，该问题是复杂系统可靠性分析与评估领域极具挑战性的技术难题.本文的总体研究目标是:针对复杂系统的结构特点，建立能够

学位

复杂系统数据转换可靠性评估置信推断

时间最优轨迹规划高效算法研究

机器人和数控机床的时间最优轨迹规划是机器人和数控机床领域重要的研究内容，对于提高加工/跟踪效率与加工精度具有重要意义。本论文针对该问题，在三种重要的情形分别提出了新

学位

机器人数控机床最优轨迹规划随机模型长加工路径多点加工

p-Laplacian的特征值及其应用

p-Laplacian频繁地出现在非牛顿流体问题以及非线性弹性问题等物理现象中，但由于其非线性性，这个看似简单的算子的特征值结构并没有完全被了解。本文以带变号权函数和带变号势

学位

非线性特征值旋转数p-Laplacian特征值结构权函数势函数

离散事件系统的Petri网控制方法研究

Petri网是一种系统描述和分析的有力工具，近年来被广泛地应用于计算机科学和离散事件系统等领域。 本文以Petri网作为离散事件系统的模型，对控制理论与方法进行了较深入的研

学位

Petri网离散事件系统不变量活性控制器

马氏过程的某些分析性质

满足半群性、连续性和压缩性的线性算子称为双参数压缩半群,间称为双参数半群.设｛P｝｛U｝分别为马尔可夫过程P（s,t,x,A）在M和L上产生的有界线性算子,它们是相互唯一确定的.｛P｝成为半群

学位

双参数半群次时齐半群预解式算子无穷小算子

非平稳信号时-频分析:Wigner-Ville分布与Radon-Wigner变换的研究与应用

非平稳信号分析与处理长期以来因受到其理论方面的限制,通常只好将非平稳信号近似为平稳信号来处理,分析和处理平稳信号的Fourier分析法无法表述非平稳信号的时-频局域性质,

学位

非平稳信号分析Fourier分析法一维时间信号映射时-频分析法Radon-Wigner变换