专栏首页arxiv.org翻译专栏团队语义中命题逻辑的参数化复杂性(CS)

团队语义中命题逻辑的参数化复杂性(CS)

本文分析了命题包含(PINC)和独立逻辑(PIND)的参数化复杂度。所关注的问题是模型检验(MC)和满足性(SAT)。这些问题的复杂性在经典(非参数化)设置中得到了很好的理解。Mahmood和Meier (FoIKS 2020)最近研究了命题依赖逻辑的参数化复杂性。作为他们工作的延续,我们对包含逻辑和独立逻辑进行了分类,从而更接近于完成命题团队语义设置中研究最多的三个逻辑的参数化复杂性。我们给出了关于8种不同参数的每个问题的结果。结果表明,对于一个基于团队的逻辑L,其L原子可以在多项式时间内计算,那么由团队规模参数化的MC是FPT。作为一个推论,我们得到了以下参数下的FPT成员:公式大小、公式深度、树宽和变量数量。对于SAT, teamsize参数表现出了有趣的行为。对于PINC, teamsize参数没有意义,而对于PDL和PIND,满足度是paraNP-complete。最后,我们证明了当参数化时,MC和SAT对于每个考虑的逻辑都是paranp完备的。

原文题目:Parameterised Complexity of Propositional Logic in Team Semantics

原文:In this work we analyse the parameterised complexity of propositional inclusion (PINC) and independence logic (PIND). The problems of interest are model checking (MC) and satisfiability (SAT). The complexity of these problems is well understood in the classical (non-parameterised) setting. Mahmood and Meier (FoIKS 2020) recently studied the parameterised complexity of propositional dependence logic (PDL). As a continuation of their work, we classify inclusion and independence logic and thereby come closer to completing the picture with respect to the parametrised complexity for the three most studied logics in the propositional team semantics setting. We present results for each problem with respect to 8 different parameterisations. It turns out that for a team-based logic L such that L-atoms can be evaluated in polynomial time, then MC parameterised by teamsize is FPT. As a corollary, we get an FPT membership under the following parameterisations: formula-size, formula-depth, treewidth, and number of variables. The parameter teamsize shows interesting behavior for SAT. For PINC, the parameter teamsize is not meaningful, whereas for PDL and PIND the satisfiability is paraNP-complete. Finally, we prove that when parameterised by arity, both MC and SAT are paraNP-complete for each of the considered logics.

原文链接:https://arxiv.org/abs/2105.14887

原文作者:Yasir Mahmood, Jonni Virtema

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 小程序开发总结01 - 模块化开发流程规范

    H5 的开发涉及开发工具、前端框架、模块管理工具、任务管理工具、UI库、接口调用工具、各种浏览器运行环境等,尽管H5丰富的开发环境给了开发者更加灵活的配置方案,...

    CS逍遥剑仙
  • 小程序开发总结01 - 模块化开发流程规范

    H5 的开发涉及开发工具、前端框架、模块管理工具、任务管理工具、UI库、接口调用工具、各种浏览器运行环境等,尽管H5丰富的开发环境给了开发者更加灵活的配置方案,...

    csxiaoyao
  • 领域驱动设计-什么是领域驱动设计和怎么使用它

    这篇文章讨论领域驱动设计(DDD),DDD是建立在面向对象分析设计上开发软件的一种方法。 通过这篇文章我们解释什么是领域驱动设计,在现代开发周期中如何实现,使用...

    用户7657330
  • 【SQL技能】SQL技能对于ETL开发人员的重要性

    我最初是一个Oracle开发者,我喜欢它的结构化查询语言,一年后,我意识到SQL并非Oracle的专有。 作为70年代Sequel标准的一个分支,SQL走向成...

    陆勤_数据人网
  • 提高代码质量:如何编写函数

    函数是实现程序功能的最基本单位,每一个程序都是由一个个最基本的函数构成的。写好一个函数是提高程序代码质量最关键的一步。本文就函数的编写,从函数命名,代码分布,技...

    哲洛不闹
  • 提高代码质量:如何编写函数

    函数是实现程序功能的最基本单位,每一个程序都是由一个个最基本的函数构成的。写好一个函数是提高程序代码质量最关键的一步。本文就函数的编写,从函数命名,代码分布,技...

    哲洛不闹
  • 巧用腾讯问卷逻辑语言DSL,复杂问卷逻辑不再愁

    作者:lzaneli  腾讯TEG前端开发工程师 |导语 腾讯问卷通过定义一套语义化的问卷逻辑语言,结合配套的问卷逻辑编辑器,让问卷调研者可以低成本、轻松、高...

    腾讯大讲堂
  • 『No24: 编写可读代码的艺术(1)』

    除了本职工作,还有点幻灯片演示设计的爱好。随着编写代码的增多,制作的的幻灯片越来越多,越来越意识到,很多事物都存在相通性。

    谢伟
  • 透过现象看本质: 常见的前端架构风格和案例

    原文链接:https://juejin.im/post/5d7ffad551882545ff173083#comment

    桃翁

扫码关注云+社区

领取腾讯云代金券