Journal
ARCHIVE FOR MATHEMATICAL LOGIC
Volume 53, Issue 7-8, Pages 835-853Publisher
SPRINGER HEIDELBERG
DOI: 10.1007/s00153-014-0391-x
Keywords
Theory of concatenation; The monadic second-order theory of two successors; Minimal essentially undecidable theory; Interpretability
Categories
Funding
- Grants-in-Aid for Scientific Research [13J10409] Funding Source: KAKEN
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available