<p>Isn't the solution a one-counter language? </p>

<p>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.</p>

<p>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.  </p>

<p>Provided of course, I read your definition in the right way.</p>

CC BY-SA 3.0
2016-02-11T11:02:49.503Z
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?
Ulrik Rasmussen
CC BY-SA 3.0
2016-02-11T11:26:33.037Z
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.
Hendrik Jan
CC BY-SA 3.0
2016-02-10T00:22:20.707Z
2016-02-10T00:22:20.707Z
Hendrik Jan
<p>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$.</p>

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

<ol>
<li>For all $1 \leq k \leq K-1$, we have $\alpha_{i_k} = \beta_{i_{k+1}}$.</li>
<li>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 <strong>not</strong> prefixes of each other</li>
</ol>

<p>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.</p>

<p>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.</p>

<p><strong>Update:</strong> Origin of the problem</p>

<p>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 <em>twinned</em> iff for all $u,v \in \Sigma^*$ and $y_1,y_2,z_1,z_2 \in \Gamma^*$ if</p>

<p>$$ 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$$</p>

<p>then either $z_1=z_2=\varepsilon$ <strong>or</strong> $|z_1|=|z_2| \neq 0$ and one of $y_1, y_2$ is a prefix of the other. [Weber &amp; 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].</p>

<p>There are effective procedures for deciding whether <em>all</em> 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.</p>

CC BY-SA 3.0
2016-02-07T07:50:22.367Z
What is the origin of this probem?
J.-E. Pin
CC BY-SA 3.0
2016-02-07T09:37:33.523Z
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.
Ulrik Rasmussen
CC BY-SA 3.0
2016-02-07T10:00:49.710Z
I have updated the question with more details.
Ulrik Rasmussen
CC BY-SA 3.0
2016-02-07T10:06:41.767Z
I was about to suggest you an approach using tranducers and then I thought it might just be the original problem...
J.-E. Pin
<reference-request><fl.formal-languages><computability><automata-theory>
A word anticorrespondence problem
Ulrik Rasmussen
# A word anticorrespondence problem

(Asked by: username_0 on 2016-02-04)

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.

**Tags:** reference-request, fl.formal-languages, computability, automata-theory
> **Comments:**
> **username_1**: What is the origin of this probem?  
> **username_0**: 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.  
> **username_0**: I have updated the question with more details.  
> **username_1**: I was about to suggest you an approach using tranducers and then I thought it might just be the original problem...  

---

## 1 answers

### Answer by username_2 on 2016-02-10. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_0**: 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?  
> **username_2**: 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.  

---

