3.9 Article

Weak theories of concatenation and minimal essentially undecidable theories

期刊

ARCHIVE FOR MATHEMATICAL LOGIC
卷 53, 期 7-8, 页码 835-853

出版社

SPRINGER HEIDELBERG
DOI: 10.1007/s00153-014-0391-x

关键词

Theory of concatenation; The monadic second-order theory of two successors; Minimal essentially undecidable theory; Interpretability

资金

  1. Grants-in-Aid for Scientific Research [13J10409] Funding Source: KAKEN

向作者/读者索取更多资源

We consider weak theories of concatenation, that is, theories for strings or texts. We prove that the theory of concatenation , which is a weak subtheory of Grzegorczyk's theory , is a minimal essentially undecidable theory, that is, the theory is essentially undecidable and if one omits an axiom scheme from , then the resulting theory is no longer essentially undecidable. Moreover, we give a positive answer to Grzegorczyk and Zdanowski's conjecture that 'The theory is a minimal essentially undecidable theory'. For the alternative theories and which have the empty string, we also prove that the each theory without the neutrality of is to be such a theory too.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

3.9
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据