Determinization

Determinization transforms a non-deterministic WFST into an equivalent deterministic one, where each state has at most one outgoing transition per input label. This enables efficient single-pass recognition and is often a prerequisite for minimization.

Terms & symbols

Defined centrally in ../NOTATION.md; repeated locally for the terms this doc uses.

Symbol	Meaning
$\oplus$ / $\otimes$	semiring plus (combine alternatives; tropical $\min$) / times (combine arcs).
$\oslash$	semiring divide (`divide` on a `DivisibleSemiring`); residual $w \oslash \min$.
$\bar{0}$ / $\bar{1}$	$\oplus$-identity ("no path") / $\otimes$-identity ("empty path", zero cost).
$\rho(q)$	final-weight function $\rho : F \to K$.
$F$	set of final states.
$\lvert Q\rvert$, $\lvert E\rvert$	number of states / transitions.

Concepts

What is a Deterministic WFST?

A WFST (Weighted Finite-State Transducer) is deterministic if:

It has exactly one start state
For each state, all outgoing transitions have distinct input labels
There are no epsilon ($\varepsilon$) transitions on the input

Non-deterministic:              Deterministic:

       a/1.0                          a/1.0
   ┌──────────► 1                 ┌──────────► 1
   │                              │
   0                              0
   │                              │
   └──────────► 2                 └──────────► 2
       a/2.0                          b/2.0

   (Two 'a' arcs)                 (Distinct labels)

Why Determinize?

Efficient recognition: Single path per input string—no backtracking needed
Prerequisite for minimization: Weighted minimization requires deterministic input
Unique path property: Simplifies lattice generation and scoring
Composition optimization: Deterministic components compose more efficiently

The Weighted Powerset Construction

Unlike classical automata theory where determinization uses simple state sets, weighted determinization uses weighted subsets—sets of (state, residual_weight) pairs (Mohri 2009):

Non-deterministic state set:  {1, 2}

Weighted subset:  {(1, 0.5), (2, 1.5)}
                    │    │     │    │
                    │    │     │    └─ residual weight for state 2
                    │    │     └─ state 2
                    │    └─ residual weight for state 1
                    └─ state 1

The residual weight tracks "how much extra weight" each original state carries compared to the minimum. The figure below shows the construction collapsing two $a$-arcs into one: the arc carries the factored-out minimum $\min(1.0, 2.0) = 1.0$ and the loser's surplus rides inside the destination subset as a residual.

Red panel = non-deterministic input (two $a$-arcs share a label); green panel = deterministic output. The arc weight is the factored-out $\min$; residuals $(\text{state}, w \oslash \min)$ live inside the subset state; double rings are final.

Text view

before (non-deterministic):           after (deterministic):

      a/1.0                                a/1.0
   ┌────────► 1 ──b/1.0──► (3)         0 ─────────► {(1,0̄),(2,1.0)} ─b/1.0─► {(3,0̄)}
   0                        ▲
   └────────► 2 ──b/1.0─────┘          arc carries min = 1.0;
      a/2.0                            residual 1.0 of state 2 rides in the subset

Core API

Types

/// Configuration for determinization
pub struct DeterminizeConfig {
    /// Maximum number of states in output (prevents runaway)
    pub max_states: Option<usize>,
    /// Whether to epsilon-remove first (recommended)
    pub remove_epsilon_first: bool,
    /// Whether to connect (trim) after determinization
    pub connect_after: bool,
}

/// Errors during determinization
pub enum DeterminizeError {
    NoStartState,
    StateLimitExceeded { limit: usize },
    NotDeterminizable { reason: String },
}

Functions

/// Determinize a WFST using weighted powerset construction
pub fn determinize<L, W, F>(
    fst: &F,
    config: DeterminizeConfig,
) -> Result<F, DeterminizeError>;

/// Check if a WFST is deterministic
pub fn is_deterministic<L, W, F>(fst: &F) -> bool;

/// Count degree of non-determinism (max same-label arcs from one state)
pub fn non_determinism_degree<L, W, F>(fst: &F) -> usize;

Examples

Basic Usage

use lling_llang::prelude::*;
use lling_llang::algorithms::{determinize, is_deterministic, DeterminizeConfig};

// Build a non-deterministic WFST
// Two 'a' transitions from state 0:
//   0 --a/1.0--> 1 --b--> 3 (final)
//   0 --a/2.0--> 2 --c--> 3 (final)
let mut fst = VectorWfst::<char, TropicalWeight>::new();
fst.add_states(4);
fst.set_start(0);
fst.add_arc(0, Some('a'), Some('a'), 1, TropicalWeight::new(1.0));
fst.add_arc(0, Some('a'), Some('a'), 2, TropicalWeight::new(2.0));
fst.add_arc(1, Some('b'), Some('b'), 3, TropicalWeight::new(1.0));
fst.add_arc(2, Some('c'), Some('c'), 3, TropicalWeight::new(1.0));
fst.set_final(3, TropicalWeight::one());

// Check: not deterministic
assert!(!is_deterministic(&fst));
assert_eq!(non_determinism_degree(&fst), 2);

// Determinize
let det_fst = determinize(&fst, DeterminizeConfig::standard())?;

// Verify: now deterministic
assert!(is_deterministic(&det_fst));

Diamond Pattern (Merging Paths)

// Diamond: two paths with same label sequence
//   0 --a/1--> 1 --b--> 3 (final)
//   0 --a/2--> 2 --b--> 3 (final)
let mut fst = VectorWfst::<char, TropicalWeight>::new();
fst.add_states(4);
fst.set_start(0);
fst.add_arc(0, Some('a'), Some('a'), 1, TropicalWeight::new(1.0));
fst.add_arc(0, Some('a'), Some('a'), 2, TropicalWeight::new(2.0));
fst.add_arc(1, Some('b'), Some('b'), 3, TropicalWeight::new(1.0));
fst.add_arc(2, Some('b'), Some('b'), 3, TropicalWeight::new(1.0));
fst.set_final(3, TropicalWeight::one());

let det_fst = determinize(&fst, DeterminizeConfig::standard())?;

// Diamond collapses to linear chain
// Result: 0 --a/1--> {1,2} --b/1--> {3}
// Fewer states than original
assert!(det_fst.num_states() <= fst.num_states());

Weight Preservation

// Non-deterministic with two paths to final states
//   0 --a/1--> 1 (final, w=0)
//   0 --a/3--> 2 (final, w=0)
let mut fst = VectorWfst::<char, TropicalWeight>::new();
fst.add_states(3);
fst.set_start(0);
fst.add_arc(0, Some('a'), Some('a'), 1, TropicalWeight::new(1.0));
fst.add_arc(0, Some('a'), Some('a'), 2, TropicalWeight::new(3.0));
fst.set_final(1, TropicalWeight::one());
fst.set_final(2, TropicalWeight::one());

let det_fst = determinize(&fst, DeterminizeConfig::standard())?;

// After determinization:
// - 'a' transition has weight 1.0 (minimum of 1.0 and 3.0)
// - Final state merges both original finals
// - Residual weights incorporated into final weight

Algorithm Details

Weighted Subset Construction

The algorithm maintains a mapping from weighted subsets to deterministic output states, expanding one subset at a time (Mohri 2009). The invariant is that each output state names a unique normalized weighted subset: for every input label leaving that subset, all destination states are gathered, their common weight factor $\oplus$-$\min$ is factored onto the arc, and the per-state surplus $w \oslash \min$ is retained as a residual so that total path weight is preserved. The literate chunks below name the three phases.

Text view

procedure DETERMINIZE(fst):
    result ← new WFST
    initial_subset ← {(fst.start, 1̄)}                 // residual 1̄ at the start
    result.start ← new_state(initial_subset)
    queue.push(result.start, initial_subset)
    while queue not empty:
        (output_state, subset) ← queue.pop()
        for (state, residual) in subset:               // final weights
            if fst.is_final(state):
                result.final[output_state] ⊕= residual ⊗ fst.final_weight(state)
        for label in input_labels(subset):             // one arc per label
            target_subset ← compute_target_subset(subset, label)
            min_w ← ⊕-min{ w : (s, w) ∈ target_subset }
            normalized ← {(s, w ⊘ min_w) : (s, w) ∈ target_subset}
            target_state ← get_or_create(normalized)
            result.add_arc(output_state, label, min_w, target_state)
    return result

⟨ seed the start subset ⟩ ≡
    initial_subset ← {(fst.start, 1̄)}
    result.start ← new_state(initial_subset)
    queue.push(result.start, initial_subset)

⟨ accumulate the final weight of a subset ⟩ ≡
    for (state, residual) in subset:
        if fst.is_final(state):
            result.final[output_state] ⊕= residual ⊗ fst.final_weight(state)

⟨ build one deterministic arc per label ⟩ ≡
    for label in input_labels(subset):
        target_subset ← compute_target_subset(subset, label)   // ⟨ move + multiply residuals ⟩
        min_w ← ⊕-min{ w : (s, w) ∈ target_subset }            // common factor
        normalized ← {(s, w ⊘ min_w) : (s, w) ∈ target_subset} // residuals
        target_state ← get_or_create(normalized)               // dedupe via subset cache
        result.add_arc(output_state, label, min_w, target_state)

⟨ weighted subset determinization ⟩ ≡
    ⟨ seed the start subset ⟩
    while queue not empty:
        (output_state, subset) ← queue.pop()
        ⟨ accumulate the final weight of a subset ⟩
        ⟨ build one deterministic arc per label ⟩
    return result

The get_or_create cache is what bounds the construction: two states reached by label sequences with identical normalized residual profiles map to the same output state, so the determinized automaton stays finite whenever the input is determinizable.

Weight Normalization

The key insight is weight normalization using the semiring's divide operation $\oslash$ (divide on a DivisibleSemiring):

Before normalization:
  target_subset = {(1, 2.0), (2, 5.0), (3, 3.0)}

Compute minimum:
  min_w = ⊕-min(2.0, 5.0, 3.0) = 2.0

Normalized (each weight divided by min, w ⊘ min_w):
  normalized = {(1, 0.0), (2, 3.0), (3, 1.0)}

Transition weight = min_w = 2.0

This ensures:

The arc carries the "common" weight factor
Residuals track the "extra" weight per original state
Total path weight is preserved

Handling Final Weights

When a weighted subset contains final states, the deterministic state's final weight combines all contributions:

$$\begin{aligned} \text{subset} &= \{(q_1, r_1), (q_2, r_2), \dots\} \\\ \text{final\_weight} &= \bigoplus_i \{\, r_i \otimes \rho(q_i) : q_i \text{ is final} \,\} \end{aligned}$$

where $\rho(q)$ is the final weight of state $q$.

Complexity

Time Complexity

Case	Complexity
Worst case	$\mathcal{O}(2^{\lvert Q\rvert})$ — exponential (powerset)
Unambiguous input	$\mathcal{O}(\lvert Q\rvert + \lvert E\rvert)$ — linear
Practical	Often near-linear for speech/NLP

Space Complexity

Structure	Size
Subset cache	$\mathcal{O}(\#\,\text{unique subsets})$
Queue	$\mathcal{O}(\#\,\text{active subsets})$
Output WFST	$\mathcal{O}(\lvert Q'\rvert + \lvert E'\rvert)$

Why Exponential Worst Case?

The powerset construction can create $2^{\lvert Q\rvert}$ subsets in pathological cases:

Exponential blowup example:

  0 → 1 → 2 → ... → n  (with alternating a/b choices)
      ↓   ↓         ↓
      1'  2'        n'

  Each state can be in or out of the subset → 2ⁿ possibilities

The max_states configuration prevents runaway:

let config = DeterminizeConfig {
    max_states: Some(1_000_000),  // Limit output size
    ..Default::default()
};

Special Cases

Epsilon Transitions

Epsilon transitions on the input make determinization more complex:

// Recommended: remove epsilon first
let config = DeterminizeConfig {
    remove_epsilon_first: true,  // Default
    ..Default::default()
};

If remove_epsilon_first is true, the algorithm handles $\varepsilon$-removal internally.

Already Deterministic Input

If the input is already deterministic, the algorithm essentially copies it:

let fst = build_deterministic_fst();
assert!(is_deterministic(&fst));

let det = determinize(&fst, DeterminizeConfig::standard())?;
// det has same structure as fst

Empty WFST

let fst: VectorWfst<char, TropicalWeight> = VectorWfst::new();
let det = determinize(&fst, DeterminizeConfig::standard())?;
assert_eq!(det.num_states(), 0);

Semiring Requirements

Determinization requires a divisible semiring:

pub trait DivisibleSemiring: Semiring {
    fn divide(&self, other: &Self) -> Option<Self>;
}

Semiring	Divisible	Division Operation
Tropical	Yes	$a \oslash b = a - b$
Log	Yes	$a \oslash b = a - b$
Probability	Yes	$a \oslash b = a / b$
Boolean	No	N/A
String	No	N/A

Why division? Weight normalization requires dividing each weight by the minimum ($w \oslash \min$) to compute residuals.

Common Patterns

Pre-Minimization Pipeline

use lling_llang::algorithms::{
    remove_epsilon, determinize, minimize,
    EpsilonRemovalConfig, DeterminizeConfig, MinimizeConfig,
};

// Standard optimization pipeline:
// 1. Remove epsilon transitions
remove_epsilon(&mut fst, EpsilonRemovalConfig::default())?;

// 2. Determinize
let det = determinize(&fst, DeterminizeConfig::standard())?;

// 3. Minimize (requires deterministic input)
let min = minimize(&det, MinimizeConfig::default())?;

Checking Before Determinizing

if !is_deterministic(&fst) {
    let det = determinize(&fst, DeterminizeConfig::standard())?;
    // Use det...
} else {
    // Already deterministic, skip
}

Measuring Non-Determinism

let degree = non_determinism_degree(&fst);

match degree {
    0 => println!("Empty WFST"),
    1 => println!("Already deterministic"),
    d => println!("Non-determinism degree: {} (max same-label arcs)", d),
}

Visualization

The before/after diagram above renders this construction; the ASCII views are kept here for reference.

Before Determinization

          a/1.0                    b/1.0
    [0] ─────────► 1 ─────────────────────► (3)
      │                                      ▲
      │                                      │
      └─────────► 2 ─────────────────────────┘
          a/2.0              c/1.0

Non-deterministic: two 'a' arcs from state 0

After Determinization

          a/1.0                    b/1.0
    [0] ─────────► {1,2} ─────────────────► ({3}, final)
                     │                       ▲
                     │                       │
                     └───────────────────────┘
                              c/1.0

Deterministic: single 'a' arc to merged state {1,2}
Arc weight = ⊕-min(1.0, 2.0) = 1.0

Weight Flow Example

Original paths for input "ab":
  Path 1: 0 --a/1--> 1 --b/2--> 3 (final)  Total: 3
  Path 2: 0 --a/3--> 2 --b/2--> 3 (final)  Total: 5

Determinized (tropical ⊕ = min):
  0 --a/1--> {1:0, 2:2} --b/2--> (final)

  After 'a': weight=1, residuals={1:0, 2:2}
  After 'b': weight=1 ⊗ 2 = 3, final with residual combination

Best path weight preserved: 3

Error Handling

use lling_llang::algorithms::DeterminizeError;

match determinize(&fst, config) {
    Ok(det) => {
        // Success - use determinized WFST
    }
    Err(DeterminizeError::NoStartState) => {
        // Input WFST has no start state
    }
    Err(DeterminizeError::StateLimitExceeded { limit }) => {
        // Output grew too large, increase max_states or simplify input
    }
    Err(DeterminizeError::NotDeterminizable { reason }) => {
        // WFST cannot be determinized (cycle issues)
    }
}

Performance Tips

Remove epsilon first: Epsilon-free WFSTs determinize faster
Set reasonable limits: Use max_states to catch blowup early
Check first: Use is_deterministic() to skip unnecessary work
Measure degree: High non_determinism_degree suggests potential blowup

References

Mohri 2009 — Weighted Automata Algorithms: weighted determinization via the weighted-subset construction, residual normalization, and the determinizability condition (twins property).
Mohri 2002 — Weighted Finite-State Transducers in Speech Recognition: determinization as a stage of the standard recognition-cascade optimization pipeline.
Allauzen 2007 — OpenFst: the reference library whose Determinize operation and DivisibleSemiring-style weight API this implementation mirrors.

Navigation Menu

Repository navigation

Determinization

Terms & symbols

Concepts

What is a Deterministic WFST?

Why Determinize?

The Weighted Powerset Construction

Core API

Types

Functions

Examples

Basic Usage

Diamond Pattern (Merging Paths)

Weight Preservation

Algorithm Details

Weighted Subset Construction

Weight Normalization

Handling Final Weights

Complexity

Time Complexity

Space Complexity

Why Exponential Worst Case?

Special Cases

Epsilon Transitions

Already Deterministic Input

Empty WFST

Semiring Requirements

Common Patterns

Pre-Minimization Pipeline

Checking Before Determinizing

Measuring Non-Determinism

Visualization

Before Determinization

After Determinization

Weight Flow Example

Error Handling

Performance Tips

References

Related Topics

FilesExpand file tree

determinization.md

Latest commit

History

determinization.md

File metadata and controls

Determinization

Terms & symbols

Concepts

What is a Deterministic WFST?

Why Determinize?

The Weighted Powerset Construction

Core API

Types

Functions

Examples

Basic Usage

Diamond Pattern (Merging Paths)

Weight Preservation

Algorithm Details

Weighted Subset Construction

Weight Normalization

Handling Final Weights

Complexity

Time Complexity

Space Complexity

Why Exponential Worst Case?

Special Cases

Epsilon Transitions

Already Deterministic Input

Empty WFST

Semiring Requirements

Common Patterns

Pre-Minimization Pipeline

Checking Before Determinizing

Measuring Non-Determinism

Visualization

Before Determinization

After Determinization

Weight Flow Example

Error Handling

Performance Tips

References

Related Topics