First-Order Concatenation Theory with Bounded Quantifiers

2020/03/10 by Kristiansen, Lars, Murwanashyaka, Juvenal
#03B10 #03B25 #FOS: Mathematics #Logic (math.LO)

paper · doi:10.48550/arxiv.2003.04964

Abstract

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.

Related

• Notes on Fragments of First-Order Concatenation Theory
• Weak Essentially Undecidable Theories of Concatenation II
• Decidability, Complexity, and Expressiveness of First-Order Logic Over the Subword Ordering
• Quantifier Alternation in Two-Variable First-Order Logic with Successor Is Decidable
• Quantifier Alternation for Infinite Words