首页    期刊浏览 2024年12月01日 星期日
登录注册

文章基本信息

  • 标题:Parameterized Complexity of CTL: Courcelle's Theorem For Infinite Vocabularies
  • 本地全文:下载
  • 作者:Martin Lück ; Arne Meier ; Irina Schindler
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2014
  • 卷号:2014
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We present an almost complete classification of the parameterized complexity of all operator fragments of the satisfiability problem in computation tree logic CTL. The investigated parameterization is the sum of temporal depth and structural pathwidth. The classification shows a dichotomy between W[1]-hard and fixed-parameter tractable fragments. The only real operator fragment which is confirmed to be in FPT is the fragment containing solely AX. Also we prove a generalization of Courcelle's theorem to infinite signatures which will be used to proof the FPT-membership case.

  • 关键词:Parameterized Complexity ; Temporal Logic
国家哲学社会科学文献中心版权所有