Notes on Fragments of First-Order Concatenation Theory

2018/04/17 by Lars Kristiansen, Kristiansen, Lars, Juvenal Murwanashyaka +1
Computer Science · #semigroups and automata theory #Logic, programming, and type systems #Advanced Algebra and Logic

paper · pdf · doi:10.48550/arxiv.1804.06367

Abstract

We identify a number of decidable and undecidable fragments of first-order concatenation theory. We also give a purely universal axiomatization which is complete for the fragments we identify. Furthermore, we prove some normal-form results.

Related

• First-Order Concatenation Theory with Bounded Quantifiers
• Weak Essentially Undecidable Theories of Concatenation II
• Generic Results for Concatenation Hierarchies
• Decidability, Complexity, and Expressiveness of First-Order Logic Over the Subword Ordering
• Fragments of first-order logic over infinite words