Minimization algorithms for sequential transducers

Research output: Contribution to journalArticle

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|) · (|Pmax| + 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 Pmax 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 languageEnglish (US)
Pages (from-to)177-201
Number of pages25
JournalTheoretical Computer Science
Volume234
Issue number1-2
DOIs
StatePublished - 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)

Fingerprint Dive into the research topics of 'Minimization algorithms for sequential transducers'. Together they form a unique fingerprint.

  • Cite this