No label defined (Q4790422)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1860694
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 1860694

      Statements

      0 references
      0 references
      2001
      0 references
      Post correspondence problem
      0 references
      combinatorics on words
      0 references
      The Post correspondence problem (PCP) is defined as follows: Given are two morphisms \(g,h\colon\Sigma^*\rightarrow\Delta^*\). The question is if there is a non-empty word \(w\) such that \(g(w)=h(w)\), i.e., if the so-called \textit{equality set} \(E(g,h)=\{\, w\in\Sigma^+ \mid g(w)=h(w) \,\}\) is non-empty. The PCP is used in many undecidability results, in particular, many undecidability results in formal language theory follow by a reduction from PCP. The PCP is one of the ``cornerstones of undecidability'' [\textit{G. Rozenberg} and \textit{A. Salomaa}, Cornerstones of undecidability (1994; Zbl 0816.68078)]. To demonstrate this, the present paper shows that every r.e.~set can be obtained from some equality set by first intersection with a regular set and then deleting some letters in the remaining words (so-called weak identity). Obviously, every concatenation of words in the equality set results in a word in the equality set. Thus, some solutions can be broken down into ``simpler'' solutions. The present paper studies different types of prime words in equality sets. Say a word from \(E(g,h)\) is F-prime (S-prime, P-prime, resp.) if removing a final subword (an arbitrary subword, a scattered subword, resp.) cannot result in another word from \(E(g,h)\). The paper surveys mainly these classes of prime solutions and some of their properties from the viewpoint of combinatorics on words. For the entire collection see [Zbl 0990.00029].
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references