首页    期刊浏览 2024年09月07日 星期六
登录注册

文章基本信息

  • 标题:An effective characterization of the alternation hierarchy in two-variable logic
  • 本地全文:下载
  • 作者:Andreas Krebs ; Howard Straubing
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2012
  • 卷号:18
  • 页码:86-98
  • DOI:10.4230/LIPIcs.FSTTCS.2012.86
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:We characterize the languages in the individual levels of the quantifier alternation hierarchy of first-order logic with two variables by identities. This implies decidability of the individual levels. More generally we show that two-sided semidirect products with J as the right-hand factor preserve decidability.
  • 关键词:FO_2; Quantifier Alternation; J; Pseudovarities; Identities
国家哲学社会科学文献中心版权所有