I work (in implementation!) with deterministic finite state automata with input and output; i.e. there are transitions (start state,input letter)$\to$(new state,output letter). Thus every state gives a transformation {words}$\to${words}.
I want to determine whether there exist two states which act identically on arbitrarily long words. Formally, consider the coarsest relation $\sim$ on the stateset such that $x\sim y$ iff there are letters $a,b$ and transitions $(x,a)\to(x',b)$ and $(y,a)\to(y',b)$ with $x'\sim y'$. I want to know if there is $x\neq y$ with $x\sim y$.
I can do this by composing the transducer with its transpose (switching input and output), minimizing, intersecting with the diagonal on the alphabet, and detecting whether a state $(x,y)$ in the product of states survives with $x\neq y$.
However, I'd very much like a faster algorithm, say of complexity $O(n\log n)$ with $n=$ number of states (the alphabet size can be assumed small).
I thought about adapting Hopcroft's (1971) algorithm, by constructing a partition of the stateset in which, initially, two states $x,y$ are in the same part iff there exists a letter $a$ with $(x,a)\to(x',b)$ and $(y,a)\to(y',b)$ for some $x',y'$, and then refining the partition; however it doesn't seem to work straight off the bat.
EDIT: here is more explicitly the relation I am interested in. Say two states $x,y$ in a transducer are weakly equivalent, $x\sim y$, if there is at least one letter $a$ such that $x,y$ have the same output on input $a$, and lead to weakly equivalent respective states. This defines uniquely weak equivalence if one asks for $\sim$ to be maximal with this property. (Beware that it is not, in general, and equivalence relation).
It may be computed as follows: start by $x\sim_0 y$ for all $x,y$; then define $x\sim_n y$ if there is a letter $a$ and transitions $(x,a)\to(x',b)$ and $(y,a)\to(y',b)$ with $x'\sim_{n-1}y'$. These are a descending sequence of relations, so must stabilize, and they stabilize to weak equivalence.
The real question I'm interested in is not how to compute $\sim$, but merely to determine whether it is non-trivial; and I want to do that in subquadratic time, ideally linear up to logarithmic terms.
