Function minimize 

pub fn minimize<W, F, M>(fst: &F) -> Result<M>
where
    W: DivisibleSemiring + Hash + Eq + Ord,
    F: Fst<W>,
    M: MutableFst<W> + Default,

Minimize a deterministic FST to canonical minimal form

Reduces the FST to the minimum number of states while preserving the accepted weighted language. Uses Brzozowski’s algorithm which is guaranteed to produce the unique canonical minimal FST for any regular language.

Requires DivisibleSemiring for weight normalization during internal determinization. Works on both deterministic and nondeterministic FSTs (non-deterministic inputs are determinized as part of the algorithm).

Complexity

• Time: O(2^V) worst case, O(V + E) typical case
  • V = number of states in input FST
  • E = number of arcs in input FST
  • Dominated by four determinization steps
  • Worst case: exponential subset construction (rare in practice)
  • Typical case: near-linear with sparse nondeterminism
• Space: O(2^V) for subset storage during determinization
  • Temporary FSTs created at each step
  • Peak memory: largest intermediate determinized FST

Algorithm

Brzozowski’s minimization (1962):

1. Reverse: Swap initial and final states, reverse all arcs
2. Determinize: Merge states with identical suffixes
3. Reverse: Swap initial and final states again
4. Determinize: Merge states with identical prefixes
5. Connect: Remove unreachable and non-coaccessible states

Key insight: Double reversal + determinization merges all equivalent states, producing the unique minimal automaton.

Performance Notes

• Deterministic input: Much faster when input is already deterministic
• Size reduction: Effectiveness depends on redundancy in original FST
• Memory usage: Creates four intermediate FSTs (reverse, det, reverse, det)
• Alternative algorithms: Direct minimization (Hopcroft, Moore) may be faster for special cases
• Preprocessing: Consider connect before minimization to remove dead states
• Best for: FSTs with significant redundancy (post-union, post-concatenation)

Examples

Basic Minimization

use arcweight::prelude::*;

// Create an FST with redundant states that accept "ab"
let mut fst = VectorFst::<TropicalWeight>::new();
let s0 = fst.add_state();
let s1 = fst.add_state();
let s2 = fst.add_state();
let s3 = fst.add_state(); // Redundant state
let s4 = fst.add_state(); // Redundant state

fst.set_start(s0);
fst.set_final(s2, TropicalWeight::one());
fst.set_final(s4, TropicalWeight::one()); // Same language as s2

// Create redundant paths
fst.add_arc(s0, Arc::new('a' as u32, 'a' as u32, TropicalWeight::one(), s1));
fst.add_arc(s1, Arc::new('b' as u32, 'b' as u32, TropicalWeight::one(), s2));

// Redundant path with same language
fst.add_arc(s0, Arc::new('a' as u32, 'a' as u32, TropicalWeight::one(), s3));
fst.add_arc(s3, Arc::new('b' as u32, 'b' as u32, TropicalWeight::one(), s4));

// Minimize merges equivalent states
let minimized: VectorFst<TropicalWeight> = minimize(&fst)?;

println!("Original: {} states, Minimized: {} states",
         fst.num_states(), minimized.num_states());
assert!(minimized.num_states() <= fst.num_states());

Optimization Pipeline

use arcweight::prelude::*;

// Demonstrates a typical FST optimization pipeline with separate functions
// Note: No single semiring in ArcWeight implements all required traits simultaneously

// For DivisibleSemiring operations (determinization, minimization)
fn optimize_divisible_fst<W: DivisibleSemiring + std::hash::Hash + Eq + Ord>(
    fst: &VectorFst<W>
) -> Result<VectorFst<W>> {
    let connected: VectorFst<W> = connect(fst)?;
    // Note: remove_epsilons requires StarSemiring, skipped for DivisibleSemiring-only
    let deterministic: VectorFst<W> = determinize(&connected)?;
    minimize(&deterministic)
}

// For StarSemiring operations (closure, epsilon handling)
fn optimize_star_fst<W: StarSemiring + std::hash::Hash + Eq + Ord>(
    fst: &VectorFst<W>
) -> Result<VectorFst<W>> {
    let connected: VectorFst<W> = connect(fst)?;
    let no_eps: VectorFst<W> = remove_epsilons(&connected)?;
    // Note: Cannot minimize star semirings without divisibility
    Ok(no_eps)
}

// Example with TropicalWeight (DivisibleSemiring + Hash + Eq + Ord)
let mut tropical_fst = VectorFst::<TropicalWeight>::new();
let s0 = tropical_fst.add_state();
let s1 = tropical_fst.add_state();
tropical_fst.set_start(s0);
tropical_fst.set_final(s1, TropicalWeight::one());
tropical_fst.add_arc(s0, Arc::new('a' as u32, 'a' as u32, TropicalWeight::one(), s1));

let optimized_tropical = optimize_divisible_fst(&tropical_fst).unwrap();
assert!(optimized_tropical.num_states() > 0);

// Example with BooleanWeight (StarSemiring + Hash + Eq + Ord)
let mut boolean_fst = VectorFst::<BooleanWeight>::new();
let s0 = boolean_fst.add_state();
let s1 = boolean_fst.add_state();
boolean_fst.set_start(s0);
boolean_fst.set_final(s1, BooleanWeight::one());
boolean_fst.add_arc(s0, Arc::new('a' as u32, 'a' as u32, BooleanWeight::one(), s1));

let optimized_boolean = optimize_star_fst(&boolean_fst).unwrap();
assert!(optimized_boolean.num_states() > 0);

Dictionary Optimization

use arcweight::prelude::*;

// Simple dictionary FST minimization
let mut dict = VectorFst::<TropicalWeight>::new();
let s0 = dict.add_state();
let s1 = dict.add_state();
dict.set_start(s0);
dict.set_final(s1, TropicalWeight::one());
dict.add_arc(s0, Arc::new('a' as u32, 'a' as u32, TropicalWeight::one(), s1));

// Minimize the dictionary FST
let minimized: VectorFst<TropicalWeight> = minimize(&dict).unwrap();
println!("Original: {} states, Minimized: {} states",
         dict.num_states(), minimized.num_states());

Errors

Returns Error::Algorithm if:

• The input FST is invalid, corrupted, or has no start state
• Memory allocation fails during any intermediate step
• The semiring doesn’t support required division operations
• Reversal, determinization, or connection operations fail
• Intermediate FSTs become too large to process

References

[1] Brzozowski, J. A. 1962. Canonical regular expressions and minimal state graphs for definite events. Mathematical Theory of Automata 12, 529-561.

[2] Mohri, M. 2009. Weighted automata algorithms. In Handbook of Weighted Automata, Springer, 213-254. https://doi.org/10.1007/978-3-642-01492-5_6

See Also

• minimize_hopcroft - $O(n \log n)$ alternative using partition refinement
• determinize - Core operation used internally (applied twice)
• reverse - Reversal operation used internally (applied twice)
• connect - Final cleanup step to remove unreachable states
• DivisibleSemiring - Required trait for weight normalization
• TropicalWeight - Compatible semiring for shortest-path problems
• LogWeight - Compatible semiring for probabilistic computations
• compose - Often benefits from minimization preprocessing