Function determinize_parallel 

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

Parallel determinization with work-stealing

This algorithm uses a work-stealing approach for parallelizing the subset construction algorithm. Each worker thread processes subsets from a shared work queue, enabling dynamic load balancing.

Algorithm

1. Initialize work queue with start subset
2. Workers steal subsets from the queue
3. Each worker:
   • Processes a subset to find outgoing transitions
   • Creates new subsets for unvisited destinations
   • Adds new subsets to the work queue
4. Workers use atomic operations to avoid conflicts
5. Result FST is assembled from all discovered states

Complexity

• Time: O(2^V / P) worst case, O((V + E) / P) typical case
• Space: O(2^V) for subset storage (same as sequential)

Examples

use arcweight::prelude::*;
use arcweight::algorithms::parallel::determinize_parallel;

let mut fst = VectorFst::<TropicalWeight>::new();
let s0 = fst.add_state();
let s1 = fst.add_state();
let s2 = fst.add_state();
fst.set_start(s0);
fst.set_final(s2, TropicalWeight::one());
// Non-deterministic: two arcs with same input label
fst.add_arc(s0, Arc::new(1, 1, TropicalWeight::new(1.0), s1));
fst.add_arc(s0, Arc::new(1, 1, TropicalWeight::new(2.0), s2));
fst.add_arc(s1, Arc::new(2, 2, TropicalWeight::new(1.0), s2));

let det: VectorFst<TropicalWeight> = determinize_parallel(&fst).unwrap();
// Result is deterministic