1
$\begingroup$

So there's following problem, that has been bugging me for the last few days:

A solution of a PCP $ i_{1},\dots,i_{n}$ with the cards $(x_{1} ,y_{1}),\dots,(x_{m}, y_{m})$ is considered as $k$-limited if for all $j\leq n$ we say that $|\; | x_{i_{1}}\dots x_{i_{j}}| - | y_{i_{1}}\dots y_{i_{j}}|\;| \leq k$.

So after every time we add another card to our sequence, the difference between the upper and lower part of the card should be $\leq k$.

Apparently it is decidable for a fixed $k$, that a PCP-instance has a $k$-limited solution. We were told that we should try solving this problem with a DFA over the input alphabet $\{1,\dots,m\}$ - where the word $ i_{1},\dots,i_{n}$ will only be accepted if it is $k$-limited.

Now my problem is that I don't know how to construct a DFA that can check if a solution is $k$-limited and a PCP-solution at the same time.

$\endgroup$
  • $\begingroup$ What does the notation $|x_{i_1},\dots,x_{i_j}|$ represent? I don't know what the meaning of $|\cdot|$ is in this context. $\endgroup$ – D.W. Jul 6 at 19:14
  • $\begingroup$ It is the length of the card's "upper part" which was layed down. For example we have a card with (001,11) - try to imagine it as a domino stone. Then $\mid x_{i_{1}},..x_{i_{j}} \mid$ is 3. $\endgroup$ – Daisy Jul 7 at 12:34
  • $\begingroup$ It's a bit unclear what you mean by "the card" when we have a sequence $x_{i_1},\dots,x_{i_j}$ of cards. Also this notation should be defined in the question. Can you edit the question to make it self-contained and define all notation in the question itself, then flag the comments as 'no longer needed'? Thank you! $\endgroup$ – D.W. Jul 7 at 16:21
  • $\begingroup$ I don't see how that definition matches the next sentence ("difference between the upper and lower part of the card") - those seem to be two different constraints. $\endgroup$ – D.W. Jul 7 at 16:22
  • $\begingroup$ You can store the difference $z$ between the upper and the lower part of the (partial) solution in the state of an automaton, since you know its length is at most $k$. You also need to store which side is sticking out. When adding a next "card" you match the part sticking out with the card, and compute which part is now sticking out. You do this only for cards that match the part sticking out. $\endgroup$ – Hendrik Jan Jul 7 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.