Questions tagged [post-correspondence]
The post-correspondence tag has no usage guidance.
6
questions
5
votes
1
answer
230
views
Post correspondence problem for finite monoids
The Post correspondence problem has the following version for finite monoids:
Input: a finite monoid $M$ and a finite list $(m_1,m_1'),\ldots, (m_n,m_n')$ of pairs of elements of $M$
Question: is ...
- 12.1k
2
votes
0
answers
450
views
Post Correspondence Problem "binary" variant
Bounded Post Correspondence Problem is defined as follows:
given list of pairs of words $ (x_1,y_1), \ldots, (x_n, y_n) $ and $K$ find sequence of indexes $i_1, \ldots, i_k$, $k \leq K$ so that $x_{...
-2
votes
1
answer
384
views
A variant of the Post Correspondence problem
Given words $\alpha_1, \ldots \alpha_n$ and $\beta_1, \ldots, \beta_n$, Post's Correspondence Problem asks if there is a sequence $i_1, \ldots, i_k$ of indices such that $\alpha_{i_1} \ldots \alpha_{...
- 1
1
vote
2
answers
230
views
Are equalizers of regular functions always regular languages? (My guess is no because PCP, but...)
Edit: I originally defined a regular function as a function computable by a Mealy machine, but Denis pointed out that that was a weaker model than what I was thinking of.
So to be more precise, by a "...
- 420
5
votes
0
answers
2k
views
Bounded Post Correspondence Problem NP-Complete Proof
I'm looking for a simple proof that shows that the Bounded-PCP problem belongs to NP-Complete as many text books say so.
It is clear to me that the problem is decidable but I cannot find any reduction ...
- 21.6k
5
votes
0
answers
522
views
Prove Post Correspondence Problem Non-Recursive Without Reduction
Given a set of pairs of words $P = \{(\alpha_1, \beta_1), \dots, (\alpha_n, \beta_n)\} \subseteq \Sigma^*\times\Sigma^*$, the Post Correspondence Problem (PCP) is to decide wether or not there are ...
- 16.5k