4
$\begingroup$

In contrast to FSM minimization which is well studied with various algorithms, theorems and has many practical applications, I'm looking for any nontrivial insight, analysis and references to the following question.

Given a FSM 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.

$\endgroup$
7
$\begingroup$

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).

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 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) 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).

$\endgroup$
10
$\begingroup$

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 for an introduction.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ better thx. if youve seen it in a ref anywhere plz cite $\endgroup$ – vzn Sep 8 '13 at 17:09
  • $\begingroup$ 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. $\endgroup$ – D.W. Sep 9 '13 at 1:20
  • $\begingroup$ 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. $\endgroup$ – Denis Sep 9 '13 at 11:15

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.