Coding in the existential theory of concatenation

DOI10.1007/BF02017493zbMath0646.03040OpenAlexW4247203646MaRDI QIDQ3789546

J. Richard Buchi, Steven Senger

Publication date: 1986

Published in: Archiv für Mathematische Logik und Grundlagenforschung (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/138054

zbMATH Keywords

existential theorydiophantineexistentially definable relation over concatenation

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Word problems, etc. in computability and recursion theory (03D40) Prefix, length-variable, comma-free codes (94A45)

Related Items

Equations in the Partial Semigroup of Words with Overlapping Products, On equations in free semigroups with certain constraints on their solutions., The expressibility of languages and relations by word equations, Undecidability of the positive \(\forall\exists^ 3\)-theory of a free semigroup, Unnamed Item, Variants and satisfiability in the infinitary unification wonderland, Coding in the existential theory of concatenation, First-order concatenation theory with bounded quantifiers, Combination techniques and decision problems for disunification, Combination techniques and decision problems for disunification, Theories of orders on the set of words, ОБ УРАВНЕНИЯХ И НЕРАВЕНСТВАХ В СЛОВАХ И ДЛИНАХ, \(\forall \exists^{5}\)-equational theory of context unification is undecidable

Cites Work

• Unnamed Item
• Equations in free semigroups
• Coding in the existential theory of concatenation
• THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP