<p>I work (in implementation!) with deterministic finite state automata with input and output; i.e. there are transitions (start state,input letter)<span class="math-container">$\to$</span>(new state,output letter). Thus every state gives a transformation {words}<span class="math-container">$\to$</span>{words}.</p>

<p>I want to determine whether there exist two states which act identically on arbitrarily long words. Formally, consider the coarsest relation <span class="math-container">$\sim$</span> on the stateset such that <span class="math-container">$x\sim y$</span> iff there are letters <span class="math-container">$a,b$</span> and transitions <span class="math-container">$(x,a)\to(x',b)$</span> and <span class="math-container">$(y,a)\to(y',b)$</span> with <span class="math-container">$x'\sim y'$</span>. I want to know if there is <span class="math-container">$x\neq y$</span> with <span class="math-container">$x\sim y$</span>.</p>

<p>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 <span class="math-container">$(x,y)$</span> in the product of states survives with <span class="math-container">$x\neq y$</span>.</p>

<p>However, I'd very much like a faster algorithm, say of complexity <span class="math-container">$O(n\log n)$</span> with <span class="math-container">$n=$</span> number of states (the alphabet size can be assumed small).</p>

<p>I thought about adapting Hopcroft's (1971) algorithm, by constructing a partition of the stateset in which, initially, two states <span class="math-container">$x,y$</span> are in the same part iff there exists a letter <span class="math-container">$a$</span> with <span class="math-container">$(x,a)\to(x',b)$</span> and <span class="math-container">$(y,a)\to(y',b)$</span> for some <span class="math-container">$x',y'$</span>, and then refining the partition; however it doesn't seem to work straight off the bat.</p>

<p>EDIT: here is more explicitly the relation I am interested in. Say two states <span class="math-container">$x,y$</span> in a transducer are weakly equivalent, <span class="math-container">$x\sim y$</span>, if there is at least one letter <span class="math-container">$a$</span> such that <span class="math-container">$x,y$</span> have the same output on input <span class="math-container">$a$</span>, and lead to weakly equivalent respective states. This defines uniquely weak equivalence if one asks for <span class="math-container">$\sim$</span> to be maximal with this property. (Beware that it is not, in general, and equivalence relation).</p>

<p>It may be computed as follows: start by <span class="math-container">$x\sim_0 y$</span> for all <span class="math-container">$x,y$</span>; then define <span class="math-container">$x\sim_n y$</span> if there is a letter <span class="math-container">$a$</span> and transitions <span class="math-container">$(x,a)\to(x',b)$</span> and <span class="math-container">$(y,a)\to(y',b)$</span> with <span class="math-container">$x'\sim_{n-1}y'$</span>. These are a descending sequence of relations, so must stabilize, and they stabilize to weak equivalence.</p>

<p>The real question I'm interested in is not how to compute <span class="math-container">$\sim$</span>, but merely to determine whether it is non-trivial; and I want to do that in subquadratic time, ideally linear up to logarithmic terms.</p>

CC BY-SA 4.0
2020-06-04T19:08:23.560Z
Apparently there are previous works on minimizing transducers.  See e.g. [this post](https://cstheory.stackexchange.com/questions/18915/how-to-minimize-a-fsm-transducer).  Have you studied them already?  If so, what have you found, and how does it fall short for your purpose?  Even if all of the full minimization algorithms are too slow for your purpose, they may use some ideas that would help.  Also, what is known about the analogous problem for ordinary DFAs?  One of the answers at that link suggests your problem might reduce to that problem (if your transducer has no epsilon transitions).
Neal Young
CC BY-SA 4.0
2020-06-04T19:32:26.043Z
Looking further, [Breslauer 1998](https://doi.org/10.1016/S0304-3975(96)00319-2) Theorem 4.1 seems to claim a nearly linear-time algorithm for full minimization.  See also [Cho'rut 2003](https://doi.org/10.1016/S0304-3975(01)00219-5), page 142.  Do any of those help?
Neal Young
CC BY-SA 4.0
2020-06-04T20:57:32.833Z
Hi @NealYoung! There is no issue on what minimization means, my automata are deterministic, so the classical Hopcroft algorithm runs in $O(n \log n)$ worst-case time, an even $O(n \log \log n)$ average. However, if I first multiply the automaton with itself, I'm up to $O(n^2)$ even ignoring the logarithmic terms.

Said differently, I define an equivalence relation in my post. It's *not* equivalence of states, but something coarser. Can it be computed in subquadratic time? The algorithm I sketched to compute it is necessarily worse than quadratic....
grok
CC BY-SA 4.0
2020-06-04T21:02:07.453Z
... Your links are welcome, but only if one reduces from my relation to state equivalence, and then one already goes beyond quadratic.
grok
CC BY-SA 4.0
2020-06-04T22:40:35.167Z
I'm misunderstanding the relation you propose then.  Can you clarify (in a comment or edit) how the equivalence relation you define in your post differs from the standard one?   By your definition, isn't it that states $x$ and $y$ are equivalent iff, given any input string $s$, the output from feeding $s$ into the transducer starting in state $x$ is the same as the output from feeding $s$ into the transducer starting at $y$?  Is that not the standard notion?  If so, why doesn't minimization apply?  Sorry if the questions are naive -- like many readers, this is not a topic I already know.
Neal Young
CC BY-SA 4.0
2020-06-05T07:55:19.390Z
Sure, I'll edit the question.
grok
CC BY-SA 4.0
2020-06-05T08:11:30.907Z
Typo *"Start by $x \sim_0 x$ ..."*?
Marzio De Biasi
CC BY-SA 4.0
2020-06-05T11:10:21.973Z
It's weird that you define your relation with "there exists a letter a". Then according to this, two states will be equivalent if there exists a long word on which they behave the same, but their behaviour might differ on other words.
Denis
CC BY-SA 4.0
2020-06-05T20:15:44.283Z
@Denis: Yes, exactly! Maybe "equivalent" is a bad choice, let's say "close". And indeed if there exists a word longer than the size of the stateset on which two states agree, then by pumping the two states are equivalent.

I presume that the relation itself is hard to compute; but hopefully detecting its non-triviality could be easier.
grok
CC BY-SA 4.0
2020-06-06T22:53:44.493Z
That edit helped, thanks.  One sentence that threw me off is still there though, namely "*I want to determine whether there exist two states which act identically on arbitrarily long words.*"  It's ambiguous whether you mean "*an* arbitrarily long word" or "*all* arbitrarily long words".. (I assumed the latter.)
Neal Young
CC BY-SA 4.0
2020-06-07T00:05:37.770Z
FWIW, unless I'm mistaken, your problem is equivalent under linear-time reductions to the following: *given a directed graph with colored edges, are there two infinite paths that start at different vertices, such that the sequence of edge colors along the two paths are the same?*  (For the "linear time" part, I'm assuming your alphabet has constant size, and that the number of colors is constant.)  My gut feeling is that this is unlikely to have a sub-quadratic time algorithm.
Neal Young
CC BY-SA 4.0
2020-06-08T07:35:55.800Z
@NealYoung that's a very good formulation! With your permission, I'll close this question and re-open it with your statement, it will probably make a lot more sense to readers.

In fact, if it helps, for my question you may assume the graph is undirected.
grok
CC BY-SA 4.0
2020-06-08T12:41:21.193Z
Sure, of course... No need to ask my permission, I think. Maybe double-check the reduction in each direction first.  It might be better to just edit the existing post -- that way your application / motivation would be included.  Plus you'd keep the existing upvotes. :-)  p.s. With undirected graphs the answer is always yes... just repeat an edge starting at either endpoint.
Neal Young
<automata-theory><minimization>
Determining if transducer automaton has two states with intersecting images, without minimizing?
grok
# Determining if transducer automaton has two states with intersecting images, without minimizing?

(Asked by: username_0 on 2020-06-04)

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.

**Tags:** automata-theory, minimization

> **Comments:**
> **username_1**: Apparently there are previous works on minimizing transducers.  See e.g. [this post](https://cstheory.stackexchange.com/questions/18915/how-to-minimize-a-fsm-transducer).  Have you studied them already?  If so, what have you found, and how does it fall short for your purpose?  Even if all of the full minimization algorithms are too slow for your purpose, they may use some ideas that would help.  Also, what is known about the analogous problem for ordinary DFAs?  One of the answers at that link suggests your problem might reduce to that problem (if your transducer has no epsilon transitions).  
> **username_1**: Looking further, [Breslauer 1998](https://doi.org/10.1016/S0304-3975(96)00319-2) Theorem 4.1 seems to claim a nearly linear-time algorithm for full minimization.  See also [Cho'rut 2003](https://doi.org/10.1016/S0304-3975(01)00219-5), page 142.  Do any of those help?  
> **username_0**: Hi @NealYoung! There is no issue on what minimization means, my automata are deterministic, so the classical Hopcroft algorithm runs in $O(n \log n)$ worst-case time, an even $O(n \log \log n)$ average. However, if I first multiply the automaton with itself, I'm up to $O(n^2)$ even ignoring the logarithmic terms.  Said differently, I define an equivalence relation in my post. It's *not* equivalence of states, but something coarser. Can it be computed in subquadratic time? The algorithm I sketched to compute it is necessarily worse than quadratic....  
> **username_0**: ... Your links are welcome, but only if one reduces from my relation to state equivalence, and then one already goes beyond quadratic.  
> **username_1**: I'm misunderstanding the relation you propose then.  Can you clarify (in a comment or edit) how the equivalence relation you define in your post differs from the standard one?   By your definition, isn't it that states $x$ and $y$ are equivalent iff, given any input string $s$, the output from feeding $s$ into the transducer starting in state $x$ is the same as the output from feeding $s$ into the transducer starting at $y$?  Is that not the standard notion?  If so, why doesn't minimization apply?  Sorry if the questions are naive -- like many readers, this is not a topic I already know.  
> **username_0**: Sure, I'll edit the question.  
> **username_2**: Typo *"Start by $x \sim_0 x$ ..."*?  
> **username_3**: It's weird that you define your relation with "there exists a letter a". Then according to this, two states will be equivalent if there exists a long word on which they behave the same, but their behaviour might differ on other words.  
> **username_0**: @username_3: Yes, exactly! Maybe "equivalent" is a bad choice, let's say "close". And indeed if there exists a word longer than the size of the stateset on which two states agree, then by pumping the two states are equivalent.  I presume that the relation itself is hard to compute; but hopefully detecting its non-triviality could be easier.  
> **username_1**: That edit helped, thanks.  One sentence that threw me off is still there though, namely "*I want to determine whether there exist two states which act identically on arbitrarily long words.*"  It's ambiguous whether you mean "*an* arbitrarily long word" or "*all* arbitrarily long words".. (I assumed the latter.)  
> **username_1**: FWIW, unless I'm mistaken, your problem is equivalent under linear-time reductions to the following: *given a directed graph with colored edges, are there two infinite paths that start at different vertices, such that the sequence of edge colors along the two paths are the same?*  (For the "linear time" part, I'm assuming your alphabet has constant size, and that the number of colors is constant.)  My gut feeling is that this is unlikely to have a sub-quadratic time algorithm.  
> **username_0**: @NealYoung that's a very good formulation! With your permission, I'll close this question and re-open it with your statement, it will probably make a lot more sense to readers.  In fact, if it helps, for my question you may assume the graph is undirected.  
> **username_1**: Sure, of course... No need to ask my permission, I think. Maybe double-check the reduction in each direction first.  It might be better to just edit the existing post -- that way your application / motivation would be included.  Plus you'd keep the existing upvotes. :-)  p.s. With undirected graphs the answer is always yes... just repeat an edge starting at either endpoint.  

---

## 0 answers

