A problem instance is a finite list of 4-tuples $(\alpha_1, u_1, v_1, \beta_1), ..., (\alpha_N, u_N, v_N, \beta_N)$, where $\alpha_i, \beta_i \in X$ come from a finite set, and each $u_i,v_i \in A^*$ are words over a finite alphabet $A$.

A solution to the problem is a sequence of indices $i_1, i_2, ..., i_K$ such that

  1. For all $1 \leq k \leq K-1$, we have $\alpha_{i_k} = \beta_{i_{k+1}}$.
  2. The words $u' = u_{i_1} u_{i_2} \cdots u_{i_K}$ and $v' = v_{i_1} v_{i_2} \cdots v_{i_K}$ are not prefixes of each other

That is, an instance is like an instance of PCP, but with restrictions on how "dominoes" can be composed, and instead of finding strings that are equal, we need strings that differ by at least one symbol.

It is not immediately obvious to me how to decide this problem, and I have not been able to find an example of it in the literature.

Update: Origin of the problem

Given a finite state transducer over input/output alphabets $\Sigma, \Gamma$ and with initial state $p^{-}$, two states $q_1, q_2$ are said to be twinned iff for all $u,v \in \Sigma^*$ and $y_1,y_2,z_1,z_2 \in \Gamma^*$ if

$$ p^{-} \stackrel{u/y_1}{\to} q_1 \stackrel{v/z_1}{\to} q_1 \text{ and } p^{-} \stackrel{u/y_2}{\to} q_2 \stackrel{v/z_2}{\to} q_2$$

then either $z_1=z_2=\varepsilon$ or $|z_1|=|z_2| \neq 0$ and one of $y_1, y_2$ is a prefix of the other. [Weber & Klemm, Economy of description for single-valued transducers, 1995]. This is equivalent to the "algebraic" definition given in [Berstel, Transductions and Context-free languages, 1979].

There are effective procedures for deciding whether all states are twinned or not. I am interested in computing all pairs of states that are not twinned. Applying the method of squaring transducers [Beal, Carton, Prieur, Sakarovitch, 2000], this reduces to deciding the problem in my question for all pairs of states.

  • 1
    $\begingroup$ What is the origin of this probem? $\endgroup$
    – J.-E. Pin
    Feb 7, 2016 at 7:50
  • 1
    $\begingroup$ It is related to the twinning property of finite state transducers. A transducer has the twinning property if all pairs of states are twinned (see Berstel's book, "Transductions and Context-Free Languages), which is equivalent to the underlying function being subsequential. There are effective procedures to decide whether all states are twinned or not. I am interested in more information, namely which states that are twinned, and which are not. $\endgroup$ Feb 7, 2016 at 9:37
  • 1
    $\begingroup$ I have updated the question with more details. $\endgroup$ Feb 7, 2016 at 10:00
  • 2
    $\begingroup$ I was about to suggest you an approach using tranducers and then I thought it might just be the original problem... $\endgroup$
    – J.-E. Pin
    Feb 7, 2016 at 10:06

1 Answer 1


Isn't the solution a one-counter language?

The succession of the domino's is easily seen as a finite state restriction. For the unequality of $u'$ and $v'$ you have to find a single position where these strings differ. Keep track of $|u'|-|v'|$ during computation on the stack. You just nondeterministically choose such a letter, on a position of the longest of $u'$ and $v'$. Then keep simulating until the shortest string comes alongside with that same position.

I know this construction from a short paper (Prefix and equality languages of rational functions are co-context-free IPL 28 (1988) 77-79): "Theorem. For every two rational functions F and G, the complement of their prefix language Pref(F,G) is a one-counter language". However that technique is a slight variation from an earlier result by J. Berstel: Every iterated morphism yields a co-cfl, Inform. Process. Lett. 22 (1986) 7-9.

Provided of course, I read your definition in the right way.

  • $\begingroup$ Quick follow-up question: This reduces the problem to checking emptiness of the one-counter language, which is decidable by reduction to emptiness for context-free grammars. Do you know of a more direct proof of this using non-deterministic one-counter automata? $\endgroup$ Feb 11, 2016 at 11:02
  • $\begingroup$ One-counter automata for me are just push-down automata with a single stack symbol (besides a special bottom symbol). Hence context-free. I am not aware of any special "direct" emptiness tests for one-counter languages. $\endgroup$ Feb 11, 2016 at 11:26

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.