<p>Recall that, in the case of finite state automata, the notion of a minimal automaton is usually meant for <em>deterministic</em> automata only; you can define it for non-deterministic ones, but then you lose two important properties:</p>

<ol>
<li><p><em>canonicity</em> (there is a unique minimal deterministic complete automaton for a given regular language, up to state renaming) and </p></li>
<li><p>the existence of <em>polynomial-time</em> algorithms (the associated problem becomes PSPACE-complete for NFA; see <a href="http://dx.doi.org/10.1137/0222067">Jiang &amp; Ravikumar, 1993</a>).</p></li>
</ol>

<p>When considering finite state transducers, you need similarily to consider `deterministic' transducers: those are called (sub-)<em>sequential</em>, and can be minimized (e.g. <a href="http://dx.doi.org/10.1016/S0304-3975(01)00219-5">Choffrut, 2003</a> for a survey).  The issue however compared to the case of automata, is that not every finite state transducer can be made sequential!  See e.g. <a href="http://dx.doi.org/10.1016/S0304-3975(01)00271-7">Béal &amp; Carton (2002)</a> for a proof of decidability of sequentiality and a construction of the equivalent sequential automaton.  </p>

<p>Note that in the more general setting of <em>weighted</em> automata, this question is still open for some semirings (<a href="http://dx.doi.org/10.1016/j.tcs.2006.01.028">Lombardy &amp; Sakarovitch, 2006</a>).</p>

CC BY-SA 3.0
2013-09-08T17:09:09.617Z
2013-09-08T17:09:09.617Z
Sylvain
<p>As you pointed out, there are several ways to define minimal transducers, but I only know of two mathematically appealing definitions.</p>

<p>The first result concerns the reduction of linear representations of recognizable series
(= defined by weighted automata). The best reference is Chapter II, Minimization, in one of these two books (the more recent is an update of the first one, with many new additions):</p>

<p>[1] J. Berstel and C. Reutenauer, <em>Noncommutative rational series with applications</em>, Encyclopedia of Mathematics and its Applications, 137. Cambridge University Press, Cambridge, 2011. xiv+248 pp. ISBN: 978-0-521-19022-0</p>

<p>(2] J. Berstel and C. Reutenauer, <em>Rational series and their languages</em>, EATCS Monographs on Theoretical Computer Science, 12. Springer-Verlag, Berlin, 1988. viii+151 pp. ISBN: 3-540-18626-3</p>

<p>In the case of sequential functions, one can adapt Nerode's construction to obtain a minimal sequential transducer. The algorithmm was first given in</p>

<p>[3] G. N. Raney, Sequential functions. <em>J. Assoc. Comput. Mach.</em> <strong>5</strong> (1958) 177-180.</p>

<p>See also Thm XII.4.2 in</p>

<p>[4] S. Eilenberg, Automata, Languages, and Machines. Vol. A, Pure and Applied Mathematics, <strong>58</strong>, Academic Press (1974)</p>

<p>The algorithm was extended to so-called subsequential functions by Choffrut. See the survey</p>

<p>[5] C. Choffrut, Minimizing subsequential transducers: a survey. Selected papers in honor of Jean Berstel. <em>Theoret. Comput. Sci.</em> <strong>292</strong> (2003), 131-143. </p>

<p>You may also have a look at
<a href="http://www.liafa.univ-paris-diderot.fr/~jep/PDF/Exposes/Sequential.pdf">A tutorial on sequential functions</a> for an introduction.</p>

CC BY-SA 3.0
2013-09-08T17:46:30.963Z
2013-09-08T17:46:30.963Z
J.-E. Pin
<p>You can view a FSM transducer from inputs $I$ to outputs $O$ as a normal FSM on alphabet $I\times O$, and use the classic minimization algorithms.</p>

<p>For instance if your transducer has transitions labelled by $i|o$, meaning "reading $i$ and outputing $o$", you can just replace the label by $(i,o)$, meaning "reading the pair $(i,o)$". If there are $\epsilon$-transitions like $\epsilon|o$, or $i|\epsilon$, you can incorporate $\epsilon$ in the alphabet (consider it as a letter), minimize, and then you can reinterpret it as an $\epsilon$-transition. </p>

<p>Notice that allowing $\epsilon$-transitions is the only way to allow input and ouptut strings to have different sizes.</p>

CC BY-SA 3.0
2013-09-08T17:09:12.797Z
better thx. if youve seen it in a ref anywhere plz cite
vzn
CC BY-SA 3.0
2013-09-09T01:20:53.733Z
Does this method of handling $\epsilon$-transitions work, i.e., lead to a minimal automaton?  It seems like some proof is needed here to show why the resulting automaton will be necessarily minimal.
D.W.
CC BY-SA 3.0
2013-09-09T11:15:41.340Z
Yes it will be minimal only with respect to the structure of the initial automaton, I just described a way to solve the problem, that won't always be optimal.
Denis
CC BY-SA 3.0
2013-09-08T14:25:56.253Z
2013-09-08T16:38:06.063Z
2013-09-08T16:38:06.063Z
Denis
<p>In contrast to <a href="http://en.wikipedia.org/wiki/DFA_minimization" rel="nofollow">FSM minimization</a> which is well studied with various algorithms, <a href="http://en.wikipedia.org/wiki/DFA_minimization" rel="nofollow">theorems</a> and has many practical applications, I'm looking for any nontrivial insight, analysis and references to the following question.</p>

<blockquote>
  <p>Given a <a href="http://en.wikipedia.org/wiki/Finite_state_transducer" rel="nofollow">FSM transducer</a>, how does one find a "minimal" equivalent transducer?</p>
</blockquote>

<p>Note that there are possibly multiple reasonable ways to define the minimal transducer. The literature maybe hasn't settled on one. Also, I'm looking for applications if some are known.</p>

<reference-request><automata-theory><regular-language><dfa><minimization>
How to minimize a FSM transducer?
vzn
# How to minimize a FSM transducer?

(Asked by: username_0 on 2013-09-08)

In contrast to [FSM minimization](http://en.wikipedia.org/wiki/DFA_minimization) which is well studied with various algorithms, [theorems](http://en.wikipedia.org/wiki/DFA_minimization) and has many practical applications, I'm looking for any nontrivial insight, analysis and references to the following question.

> Given a [FSM transducer](http://en.wikipedia.org/wiki/Finite_state_transducer), how does one find a "minimal" equivalent transducer?

Note that there are possibly multiple reasonable ways to define the minimal transducer. The literature maybe hasn't settled on one. Also, I'm looking for applications if some are known.

**Tags:** reference-request, automata-theory, regular-language, dfa, minimization

---

## 3 answers

### Answer by username_1 on 2013-09-08. Score: 7 | Accepted answer

Recall that, in the case of finite state automata, the notion of a minimal automaton is usually meant for *deterministic* automata only; you can define it for non-deterministic ones, but then you lose two important properties:

1. *canonicity* (there is a unique minimal deterministic complete automaton for a given regular language, up to state renaming) and
2. the existence of *polynomial-time* algorithms (the associated problem becomes PSPACE-complete for NFA; see [Jiang & Ravikumar, 1993](http://dx.doi.org/10.1137/0222067)).

When considering finite state transducers, you need similarily to consider `deterministic' transducers: those are called (sub-)*sequential*, and can be minimized (e.g. [Choffrut, 2003](http://dx.doi.org/10.1016/S0304-3975(01)00219-5) for a survey). The issue however compared to the case of automata, is that not every finite state transducer can be made sequential! See e.g. [Béal & Carton (2002)](http://dx.doi.org/10.1016/S0304-3975(01)00271-7) for a proof of decidability of sequentiality and a construction of the equivalent sequential automaton.

Note that in the more general setting of *weighted* automata, this question is still open for some semirings ([Lombardy & Sakarovitch, 2006](http://dx.doi.org/10.1016/j.tcs.2006.01.028)).


---

### Answer by username_2 on 2013-09-08. Score: 10

As you pointed out, there are several ways to define minimal transducers, but I only know of two mathematically appealing definitions.

The first result concerns the reduction of linear representations of recognizable series
(= defined by weighted automata). The best reference is Chapter II, Minimization, in one of these two books (the more recent is an update of the first one, with many new additions):

[1] J. Berstel and C. Reutenauer, *Noncommutative rational series with applications*, Encyclopedia of Mathematics and its Applications, 137. Cambridge University Press, Cambridge, 2011. xiv+248 pp. ISBN: 978-0-521-19022-0

(2] J. Berstel and C. Reutenauer, *Rational series and their languages*, EATCS Monographs on Theoretical Computer Science, 12. Springer-Verlag, Berlin, 1988. viii+151 pp. ISBN: 3-540-18626-3

In the case of sequential functions, one can adapt Nerode's construction to obtain a minimal sequential transducer. The algorithmm was first given in

[3] G. N. Raney, Sequential functions. *J. Assoc. Comput. Mach.* **5** (1958) 177-180.

See also Thm XII.4.2 in

[4] S. Eilenberg, Automata, Languages, and Machines. Vol. A, Pure and Applied Mathematics, **58**, Academic Press (1974)

The algorithm was extended to so-called subsequential functions by Choffrut. See the survey

[5] C. Choffrut, Minimizing subsequential transducers: a survey. Selected papers in honor of Jean Berstel. *Theoret. Comput. Sci.* **292** (2003), 131-143.

You may also have a look at
[A tutorial on sequential functions](http://www.liafa.univ-paris-diderot.fr/~jep/PDF/Exposes/Sequential.pdf) for an introduction.


---

### Answer by username_3 on 2013-09-08. Score: 4

You can view a FSM transducer from inputs $I$ to outputs $O$ as a normal FSM on alphabet $I\times O$, and use the classic minimization algorithms.

For instance if your transducer has transitions labelled by $i|o$, meaning "reading $i$ and outputing $o$", you can just replace the label by $(i,o)$, meaning "reading the pair $(i,o)$". If there are $\epsilon$-transitions like $\epsilon|o$, or $i|\epsilon$, you can incorporate $\epsilon$ in the alphabet (consider it as a letter), minimize, and then you can reinterpret it as an $\epsilon$-transition.

Notice that allowing $\epsilon$-transitions is the only way to allow input and ouptut strings to have different sizes.

> **Comments:**
> **username_0**: better thx. if youve seen it in a ref anywhere plz cite  
> **username_4**: Does this method of handling $\epsilon$-transitions work, i.e., lead to a minimal automaton?  It seems like some proof is needed here to show why the resulting automaton will be necessarily minimal.  
> **username_3**: Yes it will be minimal only with respect to the structure of the initial automaton, I just described a way to solve the problem, that won't always be optimal.  

---

