Computing #2SAT and #2UNSAT by Binary Patterns

机译：通过二进制模式计算＃2SAT和＃2UNSAT

获取原文

页面导航

摘要
著录项
相似文献
相关主题

摘要

We present some results about the parametric complexity of #2SAT and #2UNSAT, which consist on counting the number of models and falsifying assignments, respectively, for two Conjunctive Forms (2-CF's) . Firstly, we show some cases where given a formula F, #2SAT(F) can be bounded above by considering a binary pattern analysis over its set of clauses. Secondly, since #2SAT(F) = 2~n-#2UNSAT(F) we show that, by considering the constrained graph Gf of F, if Gf represents an acyclic graph then, #UNSAT(F) can be computed in polynomial time. To the best of our knowledge, this is the first time where #2UNSAT is computed through its constrained graph, since the inclusion-exclusion formula has been commonly used for computing #UNSAT(F).

机译：我们给出了有关＃2SAT和＃2UNSAT的参数复杂度的一些结果，其中包括分别计算两个合取形式（2-CF's）的模型数量和伪造分配。首先，我们展示了在给定公式F的情况下，可以通过考虑对其子句集进行二进制模式分析来限制＃2SAT（F）的范围。其次，由于＃2SAT（F）= 2〜n-＃2UNSAT（F）我们表明，通过考虑F的约束图Gf，如果Gf表示一个无环图，则#UNSAT（F）可以在多项式时间内计算。据我们所知，这是第一次通过约束图计算＃2UNSAT，因为包含-排除公式已普遍用于计算#UNSAT（F）。

著录项

来源
《Mexican conference on pattern Recognition》|2012年|273-282|共10页
会议地点 Huatulco(MX)
作者
Guillermo De Ita Luna; J. Raymundo Marcial-Romero;
展开▼
作者单位

Faculty of Computer Sciences BUAP;

Facultad de Ingenieria UAEM;

展开▼
会议组织
原文格式 PDF
正文语种
中图分类
关键词
#SAT; Binary Patterns; Enumerative Combinatorics;

机译：#SAT;二进制模式枚举组合;

相似文献

外文文献
中文文献
专利

1. Bounds and fast approximation algorithms for binary quadratic optimization problems with application to MAX 2SAT [J] . van Maaren H., Warners JP. Discrete Applied Mathematics . 2000,第1a3期

机译：二进制二次优化问题的界线和快速逼近算法在MAX 2SAT中的应用
2. Hyperdimensional Computing With Local Binary Patterns: One-Shot Learning of Seizure Onset and Identification of Ictogenic Brain Regions Using Short-Time iEEG Recordings [J] . Burrello Alessio, Schindler Kaspar, Benini Luca, IEEE Transactions on Biomedical Engineering . 2020,第2期

机译：利用局部二进制模式的超高维度计算：使用短时IEEG录制癫痫发作发作和鉴定癫痫脑区的一次性学习
3. Lung tumour detection by fusing extended local binary patterns and weighted orientation of difference from computed tomography [J] . Shakoor Mohammad Hossein Image Processing, IET . 2019,第6期

机译：通过融合扩展的局部二进制模式和加权与计算机断层扫描的方向来检测肺部肿瘤
4. Computing #2SAT and #2UNSAT by Binary Patterns [C] . Guillermo De Ita Luna, J. Raymundo Marcial-Romero Mexican Conference on Pattern Recognition . 2012

机译：通过二进制模式计算＃2SAT和＃2UNSAT
5. A comparison study of digital sinusoidal fringe generation technique: Defocusing binary patterns vs focusing sinusoidal patterns. [D] . Lei, Shuangyan. 2010

机译：数字正弦条纹生成技术的比较研究：散焦二进制模式与聚焦正弦模式。
6. Weighted full binary tree-sliced binary pattern: An RGB-D image descriptor [O] . Y.B. Ravi Kumar, C.K. Narayanappa, P. Dayananda 2020

机译：加权全二叉树切片二进制模式：RGB-D图像描述符
7. Computing #2SAT and #2UNSAT by Binary Patterns [O] . Guillermo De Ita Luna, J. Raymundo Marcial-Romero 2012

机译：通过二进制模式计算＃2SAT和＃2UNSAT
8. Patterns of Fluid Phase Behaviour in Binary and Quasi-Binary Mixtures (Patronenvan Fluiede Fasengedrag in Binaire en Quasi-Binaire Mengsels) [R] . Stamoulis, D. 1994

机译：二元和准二元混合物中流体相行为的模式（Binaire en Quasi-Binaire mengsels中的patronenvan Fluiede Fasengedrag）

Computing #2SAT and #2UNSAT by Binary Patterns

摘要

著录项

相似文献

相关主题

期刊订阅