Coding in the existential theory of concatenation

DOI10.1007/BF02017493zbMATH Open0646.03040OpenAlexW4247203646MaRDI QIDQ3789546FDOQ3789546

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

• THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP
• Title not available (Why is that?)
• Coding in the existential theory of concatenation
• Equations in free semigroups

Cited In (14)

• Theories of orders on the set of words
• Combination techniques and decision problems for disunification
• Title not available (Why is that?)
• \(\forall \exists^{5}\)-equational theory of context unification is undecidable
• On equations in free semigroups with certain constraints on their solutions.
• On equations and inequalities in words and word lengths
• Equations in the partial semigroup of words with overlapping products
• 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
• The expressibility of languages and relations by word equations

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)