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
2001
0 references
Post correspondence problem
0 references
combinatorics on words
0 references
0.84253097
0 references
0 references
0.79104215
0 references
0.78636163
0 references
0.78565276
0 references
0.7756234
0 references
0.77561146
0 references
0.75753665
0 references
0.75230575
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