First-order concatenation theory with bounded quantifiers

被引：0
作者：
Lars Kristiansen
Juvenal Murwanashyaka
机构：
[1] University of Oslo,Department of Informatics
[2] University of Oslo,Department of Mathematics
来源：
Archive for Mathematical Logic | 2021年 / 60卷
关键词：
Weak first-order theories; Concatenation theory; Bounded quantifiers; Decidability; 03B10; 03B25; 03D40; 68R15;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
We study first-order concatenation theory with bounded quantifiers. We give axiomatizations with interesting properties, and we prove some normal-form results. Finally, we prove a number of decidability and undecidability results.
引用
收藏
页码：77 / 104
页数：27
相关论文
共 18 条
[1]  
Corcoran J(1974)String theory J. Symb. Log. 39 625-637
[2]  
Frank W(2005)Undecidability without arithmetization Stud. Log. 79 163-230
[3]  
Maloney M(2014)Weak theories of concatenation and minimal essentially undecidable theories Arch. Math. Log. 53 835-853
[4]  
Grzegorczyk A(2012)Weak theories of concatenation and arithmetic Notre Dame J. Form. Log. 53 203-222
[5]  
Higuchi K(2000)The expressibility of languages and relations by word equations J. ACM 47 483-505
[6]  
Horihata Y(1977)The problem of solvability of equations in a free semigroup Math. USSR-Sb. 32 129-198
[7]  
Horihata Y(1961)Recursive unsolvability of Post’s problem of “tag” and other topics in theory of Turing machines Ann. Math. 74 437-455
[8]  
Karhumäki J(1946)A variant of a recursively unsolvable problem Bull. Am. Math. Soc. 52 264-268
[9]  
Mignosi F(1946)Concatenation as a basis for arithmetic J. Symb. Log. 11 105-114
[10]  
Plandowski W(1939)Review of Hermes [9] J. Symb. Log. 4 87-88
12