First-order concatenation theory with bounded quantifiers

DOI10.1007/S00153-020-00735-6MaRDI QIDQ2219089zbMATH OpenOpenAlexFDO

Authors Lars Kristiansen, Juvenal Murwanashyaka

Publication date 19 January 2021

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

bounded quantifiersconcatenation theorydecidabilityweak 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)

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.

Recommendations

• Decidable and undecidable fragments of first-order concatenation theory
• On undecidability of concatenation theory for one-symbol languages
• Weak essentially undecidable theories of concatenation
• Quantifiers and congruence closure
• scientific article; zbMATH DE number 408792

Cites work

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

Cited in

(8)

• Decidable and undecidable fragments of first-order concatenation theory
• 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
• scientific article; zbMATH DE number 3920432 (Why is no real title available?)
• Slicewise Definability in First-Order Logic with Bounded Quantifier Rank.
• On the Weihrauch degree of the additive Ramsey theorem
• Hilbert's tenth problem for term algebras with a substitution operator

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2219089)