First-order concatenation theory with bounded quantifiers

DOI10.1007/s00153-020-00735-6zbMath1498.03021arXiv2003.04964OpenAlexW3028542372MaRDI QIDQ2219089

Lars Kristiansen, Juvenal Murwanashyaka

Publication date: 19 January 2021

Published in: Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2003.04964

zbMATH Keywords

decidabilitybounded quantifiersconcatenation theoryweak first-order theories

Mathematics Subject Classification ID

Classical first-order logic (03B10) Decidability of theories and sets of sentences (03B25) Word problems, etc. in computability and recursion theory (03D40)

Related Items

Weak essentially undecidable theories of concatenation ⋮ Hilbert's tenth problem for term algebras with a substitution operator ⋮ On interpretability between some weak essentially undecidable theories

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Weak theories of concatenation and arithmetic
• Weak theories of concatenation and minimal essentially undecidable theories. An encounter of \(\mathsf{WTC}\) and \(\mathsf{S2S}\)
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Growing commas. A study of sequentiality and concatenation
• On interpretability in the theory of concatenation
• Decidable and undecidable fragments of first-order concatenation theory
• Undecidability without arithmetization
• The satisfiability of word equations: decidable and undecidable theories
• Coding in the existential theory of concatenation
• THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP
• The expressibility of languages and relations by word equations
• The Undecidability of the Generalized Collatz Problem
• A variant of a recursively unsolvable problem
• Concatenation as a basis for arithmetic
• String theory

This page was built for publication: First-order concatenation theory with bounded quantifiers