arcweight 0.3.0

//! Semiring implementations for weighted finite-state transducers.
//!
//! This module provides algebraic structures called *semirings* that define the weight
//! systems for weighted FSTs. A semiring generalizes the notions of addition and
//! multiplication while relaxing some requirements of traditional arithmetic, enabling
//! a unified framework for diverse computational problems.
//!
//! # Mathematical Foundation
//!
//! A **semiring** is an algebraic structure $`(K, \oplus, \otimes, \bar{0}, \bar{1})`$ where:
//!
//! - $`K`$ is a set of elements (weights)
//! - $`\oplus : K \times K \to K`$ is the **addition** operation (combining alternatives)
//! - $`\otimes : K \times K \to K`$ is the **multiplication** operation (extending paths)
//! - $`\bar{0} \in K`$ is the **additive identity** (represents "no path" or impossibility)
//! - $`\bar{1} \in K`$ is the **multiplicative identity** (represents "free" or zero-cost)
//!
//! ## Semiring Axioms
//!
//! For all $`a, b, c \in K`$:
//!
//! 1. **$(K, \oplus, \bar{0})$ is a commutative monoid:**
//!    - Associativity: $`(a \oplus b) \oplus c = a \oplus (b \oplus c)`$
//!    - Commutativity: $`a \oplus b = b \oplus a`$
//!    - Identity: $`a \oplus \bar{0} = \bar{0} \oplus a = a`$
//!
//! 2. **$(K, \otimes, \bar{1})$ is a monoid:**
//!    - Associativity: $`(a \otimes b) \otimes c = a \otimes (b \otimes c)`$
//!    - Identity: $`a \otimes \bar{1} = \bar{1} \otimes a = a`$
//!
//! 3. **$\otimes$ distributes over $\oplus$:**
//!    - Left: $`a \otimes (b \oplus c) = (a \otimes b) \oplus (a \otimes c)`$
//!    - Right: $`(a \oplus b) \otimes c = (a \otimes c) \oplus (b \otimes c)`$
//!
//! 4. **$\bar{0}$ is an annihilator for $\otimes$:**
//!    - $`a \otimes \bar{0} = \bar{0} \otimes a = \bar{0}`$
//!
//! # Available Semirings
//!
//! ## [`TropicalWeight`] — Tropical Semiring $`(\mathbb{R} \cup \{+\infty\}, \min, +, +\infty, 0)`$
//!
//! | Operation | Definition |
//! |-----------|------------|
//! | $`a \oplus b`$ | $`\min(a, b)`$ |
//! | $`a \otimes b`$ | $`a + b`$ |
//! | $`\bar{0}`$ | $`+\infty`$ |
//! | $`\bar{1}`$ | $`0`$ |
//!
//! **Use cases:** Shortest path, Viterbi decoding, edit distance, cost minimization
//!
//! ## [`LogWeight`] — Log Semiring $`(\mathbb{R} \cup \{+\infty\}, \oplus_{\log}, +, +\infty, 0)`$
//!
//! | Operation | Definition |
//! |-----------|------------|
//! | $`a \oplus b`$ | $`-\log(e^{-a} + e^{-b})`$ |
//! | $`a \otimes b`$ | $`a + b`$ |
//! | $`\bar{0}`$ | $`+\infty`$ |
//! | $`\bar{1}`$ | $`0`$ |
//!
//! **Use cases:** Numerically stable probability computation, speech recognition, machine translation
//!
//! ## [`ProbabilityWeight`] — Probability Semiring $`([0, 1], +, \times, 0, 1)`$
//!
//! | Operation | Definition |
//! |-----------|------------|
//! | $`a \oplus b`$ | $`a + b`$ |
//! | $`a \otimes b`$ | $`a \times b`$ |
//! | $`\bar{0}`$ | $`0`$ |
//! | $`\bar{1}`$ | $`1`$ |
//!
//! **Use cases:** Direct probability computation, language models, Bayesian inference
//!
//! ## [`RealWeight`] — Real Semiring $`(\mathbb{R}, +, \times, 0, 1)`$
//!
//! | Operation | Definition |
//! |-----------|------------|
//! | $`a \oplus b`$ | $`a + b`$ |
//! | $`a \otimes b`$ | $`a \times b`$ |
//! | $`\bar{0}`$ | $`0`$ |
//! | $`\bar{1}`$ | $`1`$ |
//!
//! **Use cases:** Linear algebra, normalization, matrix operations, signal processing
//!
//! ## [`BooleanWeight`] — Boolean Semiring $`(\{0, 1\}, \vee, \wedge, 0, 1)`$
//!
//! | Operation | Definition |
//! |-----------|------------|
//! | $`a \oplus b`$ | $`a \vee b`$ (OR) |
//! | $`a \otimes b`$ | $`a \wedge b`$ (AND) |
//! | $`\bar{0}`$ | $`\mathrm{false}`$ |
//! | $`\bar{1}`$ | $`\mathrm{true}`$ |
//!
//! **Use cases:** Unweighted automata, membership testing, regular expressions
//!
//! ## [`IntegerWeight`] — Integer Semiring $`(\mathbb{Z}, +, \times, 0, 1)`$
//!
//! | Operation | Definition |
//! |-----------|------------|
//! | $`a \oplus b`$ | $`a + b`$ |
//! | $`a \otimes b`$ | $`a \times b`$ |
//! | $`\bar{0}`$ | $`0`$ |
//! | $`\bar{1}`$ | $`1`$ |
//!
//! **Use cases:** Counting paths, exact arithmetic, combinatorial applications
//!
//! ## [`StringWeight`] — String Semiring $`(\Sigma^*, \mathrm{lcp}, \cdot, \bot, \varepsilon)`$
//!
//! | Operation | Definition |
//! |-----------|------------|
//! | $`a \oplus b`$ | longest common prefix |
//! | $`a \otimes b`$ | string concatenation |
//! | $`\bar{0}`$ | special marker |
//! | $`\bar{1}`$ | empty string $`\varepsilon`$ |
//!
//! **Use cases:** String operations, edit sequences, sequence alignment
//!
//! ## [`MinWeight`] / [`MaxWeight`] — MinMax Semirings
//!
//! Lattice-based semirings for optimization problems.
//!
//! ## [`ProductWeight`] — Product Semiring $`(K_1 \times K_2, \oplus, \otimes)`$
//!
//! Combines two semirings into a Cartesian product with component-wise operations.
//!
//! **Use cases:** Multi-objective optimization, simultaneous cost/probability tracking
//!
//! ## [`GallicWeight`] — Gallic Semiring
//!
//! Combines label sequences with weights for FST composition and output tracking.
//! Available variants: [`LeftGallic`], [`RightGallic`], [`MinGallic`], [`RestrictGallic`], [`UnionGallic`].
//!
//! # Choosing a Semiring
//!
//! ```
//! use arcweight::prelude::*;
//!
//! // For shortest path / minimum cost
//! let tropical = TropicalWeight::new(0.5);
//!
//! // For probabilistic models (log domain)
//! let log_prob = LogWeight::new(-2.3); // log probability
//!
//! // For direct probabilities
//! let prob = ProbabilityWeight::new(0.8);
//!
//! // For unweighted automata
//! let boolean = BooleanWeight::new(true);
//!
//! // Arithmetic follows semiring properties
//! let sum = tropical + TropicalWeight::new(0.3); // min(0.5, 0.3) = 0.3
//! let product = tropical * TropicalWeight::new(0.2); // 0.5 + 0.2 = 0.7
//! ```
//!
//! # Specialized Properties
//!
//! Some semirings provide additional structure enabling specialized algorithms:
//!
//! - [`DivisibleSemiring`]: Supports division operation for weight pushing
//! - [`StarSemiring`]: Supports Kleene closure $`w^* = \bigoplus_{i=0}^{\infty} w^i`$
//! - [`NaturallyOrderedSemiring`]: Has a compatible partial order
//! - [`InvertibleSemiring`]: All non-zero elements have multiplicative inverses
//!
//! # References
//!
//! - Kuich, W., & Salomaa, A. (1986). *Semirings, Automata, Languages*. EATCS Monographs
//!   on Theoretical Computer Science, Vol. 5. Springer-Verlag.
//!
//! - Mohri, M. (2002). Semiring frameworks and algorithms for shortest-distance problems.
//!   *Journal of Automata, Languages and Combinatorics*, 7(3), 321–350.
//!
//! - Mohri, M., Pereira, F., & Riley, M. (2002). Weighted finite-state transducers in
//!   speech recognition. *Computer Speech & Language*, 16(1), 69–88.
//!
//! - Goodman, J. (1999). Semiring parsing. *Computational Linguistics*, 25(4), 573–605.

mod boolean;
pub mod gallic;
mod integer;
mod log;
mod minmax;
mod probability;
mod product;
mod real;
mod string;
mod traits;
mod tropical;

pub use boolean::BooleanWeight;
pub use integer::IntegerWeight;
pub use log::LogWeight;
pub use minmax::{MaxWeight, MinWeight};
pub use probability::ProbabilityWeight;
pub use product::ProductWeight;
pub use real::RealWeight;
pub use string::StringWeight;
pub use traits::*;
pub use tropical::TropicalWeight;

// Re-export gallic types for convenience
pub use gallic::{
    GallicWeight, LeftGallic, LeftGallicWeight, MinGallic, MinGallicWeight, RestrictGallic,
    RestrictGallicWeight, RightGallic, RightGallicWeight, StandardGallicWeight, UnionGallic,
};