首页    期刊浏览 2024年11月28日 星期四
登录注册

文章基本信息

  • 标题:Conservative Extensions in Guarded and Two-Variable Fragments
  • 本地全文:下载
  • 作者:Jean Christoph Jung ; Carsten Lutz ; Mauricio Martel
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2017
  • 卷号:80
  • 页码:108:1-108:14
  • DOI:10.4230/LIPIcs.ICALP.2017.108
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:We investigate the decidability and computational complexity of (deductive) conservative extensions in fragments of first-order logic (FO), with a focus on the two-variable fragment FO2 and the guarded fragment GF. We prove that conservative extensions are undecidable in any FO fragment that contains FO2 or GF (even the three-variable fragment thereof), and that they are decidable and 2ExpTime-complete in the intersection GF2 of FO2 and GF.
  • 关键词:Conservative Extensions; Decidable Fragments of First-Order Logic; Computational Complexity
国家哲学社会科学文献中心版权所有