【摘 要】
:
对于一种逻辑(?),它在一类结构C上的模型检测问题是询问一个给定的(?)语句在一个给定的C结构中是否成立。核化是一个在设计固定参数算法中广泛应用的技术。核是一个从输入实
论文部分内容阅读
对于一种逻辑(?),它在一类结构C上的模型检测问题是询问一个给定的(?)语句在一个给定的C结构中是否成立。核化是一个在设计固定参数算法中广泛应用的技术。核是一个从输入实例中计算并输出同一个问题的等价实例的多项式算法,而且要求输出实例的大小和参数都是输入实例参数的函数。本文中,我们通过核化技术研究一些一阶逻辑子逻辑(通过限定一阶逻辑的布尔连接词和量词得到的逻辑)的模型检测问题的参数复杂性。本文中引用了最近提出的蒸馏机制。首先我们证明了正存在式一阶逻辑在二分图上的参数模型检测问题存在线性核,其中参数为输入语句的长度。其次,在相同的参数情况下,我们证明了存在式一阶逻辑在路径上的参数模型检测问题有线性核。最后,在的假设下,对于固定的结构,我们证明了存在式或全称式一阶逻辑的参数模型检测问题没有多项式核,此时的参数为语句中的变元个数。
其他文献
失衡数据集是数据挖掘领域中广泛存在数据状态,由于不同类别的数据样本数量差异悬殊而使得正常的分类算法效果不明显。在数据挖掘领域中还有一个不可避免的问题就是数据缺失,
随着嵌入式系统以及多媒体技术的高速发展,使用嵌入式技术来实现视频点播、视频会议、视频监控等功能己经成为现在的研究热点。这样的嵌入式系统一般都具有功耗低、成本低、
随着互联网的高速发展,网络信息爆炸式增长,于此相比,互联网中的知识却相当匮乏。在此背景下,基于Web2.0的各种交互式百科知识网站应运而生并发展壮大,为用户提供了大量的有
在一个大规模分布式系统中,为了能够减少失效节点所造成的计算损失,基于卷回恢复的容错技术得到了广泛使用,其中具有代表性的如检查点技术。在设计检查点协议过程中一个关键问题
随着信息社会的发展,拥有海量数据的复杂网络不断出现,如何从这些网络中挖掘出有价值的信息是一个十分艰巨的任务。链接预测是数据挖掘领域的重要分支,也是社会网络分析的关
随着互联网的迅速发展和广泛普及,在很大程度上改变了人们的生活方式,人们不仅被动接受信息,还能与外界进行交互。互联网逐渐成为一种交互式媒体,更多的人通过博客B、BS等网
本文在分析国内外超声诊断仪市场现状后,提出一种基于ARM9的便携式B超仪器设计方案,旨在满足特殊医疗环境下对超声诊断仪的需求。
论文首先分析超声诊断仪的基本原理和结
高清化和智能化是视频监控系统发展的趋势,也是衡量系统优劣的重要标准。高清化主要反映在分辨率上,而智能化主要体现在后期的视频处理上。本文从系统架构设计与实现的角度提
在未来的网络发展中,无线网络将演变成一种支持全IP、基于多种无线网络接入技术的无缝融合异构网络,它们在覆盖范围、接入能力等方面各不相同,没有一种单一的网络可以在带宽
集成无线通信、嵌入式计算、传感器和分布式信息处理技术的无线传感器网络已经成为当前信息网络研究的热点,随着廉价的CMOS摄像头及微型麦克风的出现,以及人们对图像、音频和