### Abstract

We present general algorithms for minimizing sequential finite-state transducers that output strings or numbers. The algorithms are shown to be efficient since in the case of acyclic transducers and for output strings they operate in O(S + |E| + |V| + (|E| - |V| + |F|) · (|P_{max}| + 1)) steps, where S is the sum of the lengths of all output labels of the resulting transducer, E the set of transitions of the given transducer, V the set of its states, F the set of final states, and P_{max} one of the longest of the longest common prefixes of the output paths leaving each state of the transducer. The algorithms apply to a larger class of transducers which includes subsequential transducers.

Original language | English (US) |
---|---|

Pages (from-to) | 177-201 |

Number of pages | 25 |

Journal | Theoretical Computer Science |

Volume | 234 |

Issue number | 1-2 |

DOIs | |

State | Published - Mar 6 2000 |

### Keywords

- Finite automata
- Finite-state transducers
- Rational power series
- Semiring
- Shortest-paths algorithms

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)