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

existential theorydiophantineexistentially definable relation over concatenation

Mathematics Subject Classification ID

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

Cites work

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

Cited in

(14)

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

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)