Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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:
canonicity (there is a unique minimal deterministic complete automaton for a given regular language, up to state renaming) and
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).
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.
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.
