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

文章基本信息

  • 标题:Piecewise testable tree languages
  • 本地全文:下载
  • 作者:Mikołaj Bojańczyk ; Luc Segoufin ; Howard Straubing
  • 期刊名称:Logical Methods in Computer Science
  • 印刷版ISSN:1860-5974
  • 电子版ISSN:1860-5974
  • 出版年度:2012
  • 卷号:8
  • 期号:3
  • 页码:1
  • DOI:10.2168/LMCS-8(3:26)2012
  • 出版社:Technical University of Braunschweig
  • 摘要:This paper presents a decidable characterization of tree languages that can be defined by a boolean combination of Sigma_1 sentences. This is a tree extension of the Simon theorem, which says that a string language can be defined by a boolean combination of Sigma_1 sentences if and only if its syntactic monoid is J-trivial.
  • 其他关键词:First-order logic on trees,algebra
国家哲学社会科学文献中心版权所有