Coding in the existential theory of concatenation

DOI10.1007/BF02017493MaRDI QIDQ3789546zbMATH OpenOpenAlexFDO

Authors 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

diophantineexistential theoryexistentially definable relation over concatenation

Mathematics Subject Classification ID

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

Cites work

• Coding in the existential theory of concatenation
• Equations in free semigroups
• scientific article; zbMATH DE number 3590511 (Why is no real title available?)
• THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP

Cited in

(14)

• On interpretability in the theory of concatenation
• \(\forall \exists^{5}\)-equational theory of context unification is undecidable
• Undecidability of the positive \(\forall\exists^ 3\)-theory of a free semigroup
• First-order concatenation theory with bounded quantifiers
• Equations in the partial semigroup of words with overlapping products
• Theories of orders on the set of words
• Coding in the existential theory of concatenation
• The expressibility of languages and relations by word equations
• Combination techniques and decision problems for disunification
• scientific article; zbMATH DE number 7120897 (Why is no real title available?)
• On equations and inequalities in words and word lengths
• Variants and satisfiability in the infinitary unification wonderland
• Combination techniques and decision problems for disunification
• On equations in free semigroups with certain constraints on their solutions.

This page was built for publication: Coding in the existential theory of concatenation

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