Welcome to the documentation for lling-llang, a semiring-generic Weighted Finite-State Transducer (WFST) framework for text normalization, grammar/code correction, speech recognition, differentiable decoding, and constrained generation.
use lling_llang::prelude::*;
// Build a correction lattice
let backend = HashMapBackend::new();
let mut builder = LatticeBuilder::<TropicalWeight, _>::new(backend);
builder.add_correction(0, 1, "the", TropicalWeight::new(0.5), EdgeMetadata::original());
builder.add_correction(0, 1, "teh", TropicalWeight::new(0.0), EdgeMetadata::correction(1));
let mut lattice = builder.build(1);
// Find the best correction
let result = viterbi(&mut lattice);
if result.success {
println!("Best: {:?}", result.path.to_words(&lattice));
}Read these first — they govern every doc and are the canonical references:
| Document | Description |
|---|---|
| Style guide | Authoring rules: MathJax LaTeX in GitHub inline-math and fenced-math delimiters, define-before-use, literate pseudocode, diagram embedding, citations |
| Notation & glossary | Every symbol ( |
| Bibliography | Citation-checked references with verified DOIs |
| Diagramming conventions | Tool-per-concept matrix, color palette, and the make diagrams render pipeline |
| Architecture · Changelog · Contributing | Repository-level entry points |
Core concepts and design of the framework:
| Document | Description |
|---|---|
| Overview | High-level architecture and component relationships |
| Semirings | Algebraic weight structures (Tropical, Log, Probability, String, Expectation, …) |
| Dynamic Semirings | Safe host-defined weight algebras: capability negotiation, token ownership, lock-free callback admission, batching, and law validation |
| Dynamic Lattices | Safe host-defined join/meet values: retained ownership, domain validation, nonblocking callback admission, bounded folds, and law probes |
| Arctic / max-plus | Maximum-score paths with gains, penalties, and explicit positive-cycle behavior |
| Signed Tropical Semiring | Extended tropical semiring with negative weights (rewards) |
| Power Semiring |
|
| WFST Operations | Rational (union, concat, closure) and unary (invert, project, reverse) operations |
| Lattices | Weighted DAGs representing correction alternatives |
| WFST Traits | Trait hierarchy for finite-state transducers |
| Lazy WFST Lifecycle | Exact expansion, retry, cancellation, snapshot, concurrency, and stack-safety semantics |
| Backends | Storage abstraction and implementations |
| Resource ABI | The scalar-WFST binding layer: providers, capture-once snapshots, the lazy composition product, the registry, and the raw-u32 status wire |
| Stack-safe execution | Formal-first typed heap machines, SCC-wide recursion elimination, lifecycle safety, work/allocation bounds, concurrency, and evidence traceability |
| Foreign-language bindings | C, C++, JavaScript, TypeScript, and ClojureScript package guides, executable evidence, ownership laws, and documentation governance |
| Dictionary providers | Feed retained libdictenstein or custom host dictionaries into bounded liblevenshtein correction without reconstructing their keys |
| Layers | Correction-layer pipeline architecture |
| Lattice Bridge | Semiring↔lattice bridge: semirings as libdictenstein dictionary values |
Core WFST algorithms (presented in literate-programming pseudocode):
| Document | Description |
|---|---|
| Path Extraction | Viterbi, N-best, and beam search |
| Shortest Distance | Single-source / all-pairs shortest distance with queue disciplines |
| Weight Pushing | Weight normalization for beam-search optimization |
| Epsilon Removal | Remove |
| Determinization | Non-deterministic → deterministic WFSTs |
| Minimization | Minimize WFST states and transitions |
| Synchronization | Normalize input/output label delay |
| Parsing | Earley parser over lattice input |
| Composition | Lazy FST and CFG composition operators |
| Topological Sort | Kahn's algorithm for DAG ordering |
| Path Sampling | Random path sampling for Monte-Carlo methods |
| RRWM | Rational Randomized Weighted-Majority for online ensemble learning |
Automata beyond the basic WFST:
| Document | Description |
|---|---|
| Overview | Comparison of the transducer families |
| Multitape Transducers |
|
| Pushdown Automata | Weighted PDAs |
| Tree Transducers | Weighted tree transducers |
| Neural Transducer (RNN-T) | Encoder–predictor–joiner; the |
| Subsequential Transducers | Deterministic transducers with piecewise decomposition |
WFST-based correction and natural-language tooling:
| Document | Description |
|---|---|
| Error Models | Edit-distance, confusion-matrix, and homophone transducers |
| Multilingual | Code-switching transducers and language identification |
| Text Normalization (TN/ITN) | Semiotic-class normalization and its inverse |
| Constrained Decoding | Grammar-constrained LLM decoding (CFG→PDA→token mask) |
| API Migration | Automated code migration between API versions |
| Syntax Repair | WFST syntax-error recovery via a ParserBackend |
Speech recognition, deep learning, and acceleration:
| Document | Description |
|---|---|
| CTC Topologies | CTC graph structures (Correct, Compact, Minimal, Selfless) |
| Differentiable Operations | Gradients through WFST operations |
| Top-Down Autograd | k2-style efficient gradients via arc posteriors |
| Deep Learning Integration | WFST layers, token graphs, lexicon marginalization |
| ASR Pipeline | Speech-recognition cascade |
| Beam Optimization | Log-semiring pushing, lookahead, token grouping |
| GPU Acceleration | CSR format, atomic recombination, batched streaming |
| SIMD | Vectorized weight operations (AVX-512/AVX2/SSE/NEON) |
| Document | Description |
|---|---|
| Acoustic Overview |
AcousticModel trait, transition matrices, score fusion |
| Cascade Construction | Full ASR cascade |
| Subword Lexicon | BPE/subword lexicon builder for ASR |
| Document | Description |
|---|---|
| Weak Supervision | Training with noisy transcripts (bypass arcs) and LF-MMI |
Specialized WFST optimizations. (The scientific benchmark journal and the phase-by-phase implementation ledger are frozen historical records — see Archive below.)
| Document | Description |
|---|---|
| Lookahead Tables | Pushing reachable weight to a pruning frontier |
| N-gram Back-off | Back-off |
| Token Grouping | LET-Decoder lazy-evaluation token grouping |
| Categorical Optimizer Contract | Typed morphisms, exact rewrite witnesses, fibers, local monoids, ownership boundaries, and performance consequences |
| Plan, Concurrency, and Provenance | Rank-certified DAG syntax, stack-safe wavefront execution, budgets, cancellation, ordered commit, and publication |
| Formal Verification | Rocq, TLA+/TLC, Z3, and Kani evidence with finite bounds, negative controls, and reproduction |
| Certified Strong Bisimulation | Validated labelled semantics, Valmari refinement, replay certificates, modal witnesses, canonical output, stack safety, resource bounds, and 83 traced obligations |
| libcpg Dataflow, Graph, and Assurance Contract | Lawful llattice v2 migration, exact libvgraph quotient semantics, stack/work bounds, and independently bound assurance evidence |
| libcpg Manifest and Durable-Fact Contract | Exact extractor manifests, durable fact identities, dense-index correspondence, source evidence, deterministic exports, cache invalidation, and adapter ownership |
| Provider-Neutral Boundary Contract | Canonical artifact identity, non-promoting provider results, limitation propagation, independent guarantees, native ownership, and the optional one-way libcpg-to-lling-llang public-API boundary |
| Neutral Vinary Foundation Contract | RegresSpec-driven ownership, canonical/schema/content identity, neutral graphs, runtime and assurance gates, stack-safe concurrency, and 77 formally traced pre-implementation obligations |
| Dictionary Surface Contract | Split libdictenstein/llattice and dictionary/fuzzy adapters, categorical semantics, required capabilities, parallel execution, and formal gates |
Frozen, dated scientific records preserved in their original notation — see
archive/README.md:
| Document | Description |
|---|---|
| Optimization Journal | Scientific benchmark ledger (hypotheses, results, post-mortems) |
| Implementation Ledger | Phase-by-phase implementation record (phases 1–7) |
| Industry-Standard & SOTA Review | Point-in-time optimization / state-of-the-art review |
Correction-layer implementations:
| Document | Description |
|---|---|
| Code Correction: Overview · Syntax Recovery · Pattern-Aware · Configuration | Pattern-aware code correction for Python, Rust, Rholang, MeTTa |
| LaTeX: Overview · Grammar · Repair · Validator | LaTeX syntax correction (CFG filtering, brace/math-mode validation) |
| MathML: Overview · Checker · Homoglyph · Types | Content-MathML semantic type checking and homoglyph disambiguation |
| Document | Description |
|---|---|
| Integration Overview | Index + the external-repository link convention |
| liblevenshtein: Overview · Dictionaries · Fuzzy Collections · Transducers · Integration | Levenshtein automata and fuzzy lookup |
| libgrammstein: Phonetic Rescoring | Phonetic lattice rescoring with Zompist rules |
| F1R3FLY.io: Vision · PathMap · MeTTaIL · MORK · MeTTaTron · Rholang | Distributed correction over the F1R3FLY stack |
| External: Speech/NLP · Text Correction · Library Usage | Integrating lling-llang into external systems |
| Document | Description |
|---|---|
| ABI Trust Model | Foreign scalar-WFST providers as untrusted input: validation duties, the F1 case study, panic containment, threading trust, residual assumptions |
| Document | Description |
|---|---|
| Release operations | Immutable release-branch tagging, exact dependency graph, validate-only evidence, single-registry dispatch, npm promotion, and failure recovery |
| Document | Description |
|---|---|
| C ABI Reference | The 61-function lling_* C ABI: dynamic algebra consumers, WFST/resource operations, typed metadata, cancellation, statuses, ownership, threading, and complexity |
| Semiring Reference | Semiring, DivisibleSemiring, StarSemiring |
| WFST Reference | Wfst, MutableWfst, LazyWfst |
| Lattice Reference | Lattice, LatticeBuilder, EdgeMetadata |
| Backend Reference | LatticeBackend, HashMapBackend |
| Path Reference | viterbi, nbest, beam_search |
| Layer Reference | CorrectionLayer, LayerPipeline |
| Feature | Description |
|---|---|
default |
Standalone WFST framework, no external dependencies |
levenshtein |
Integration with liblevenshtein for lexical correction |
lattice |
Semiring↔lattice bridge (lling-llang semirings as libdictenstein dictionary values) |
lattice-persistent |
serde-bounded dictionary values for disk-backed (persistent-artrie) dictionaries |
pcfg |
(reserved — no effect yet) Probabilistic context-free grammar support |
error-grammar |
(reserved — no effect yet) Predefined error grammars |
pos-tagging |
POS-tagging correction layer |
lm-rerank |
Language-model reranking layer |
phonetic-rescore |
Phonetic rescoring layer (requires levenshtein) |
code-correction |
Pattern-aware code syntax-recovery layer |
latex-syntax |
LaTeX syntax-correction layer |
mathml-semantic |
MathML semantic / homoglyph layer |
f1r3fly |
F1R3FLY.io integration surface: PathMap backend + MeTTaIL type layer (MORK/MeTTaTron are roadmap — see integration/f1r3fly) |
sexpr |
(reserved — no effect yet) S-expression path format for MORK compatibility |
pathmap-backend |
PathMap-optimized lattice backend |
serde |
Serialization support |
test-utils |
Expose the test_utils module (proptest strategies, fixtures) downstream |
Text view
┌─────────────────────────────────────────────────────────────────────────┐
│ Correction Layer Stack │
├─────────────────────────────────────────────────────────────────────────┤
│ Layer N: [User-Defined] ← Implement CorrectionLayer trait │
│ ↑ │
│ Layer 3: CFG Grammar ← Syntactic filtering │
│ ↑ │
│ Layer 1: Lexical Correction ← Levenshtein + phonetic candidates │
│ ↑ │
│ [Input Lattice] │
└─────────────────────────────────────────────────────────────────────────┘
New to WFSTs?
- Semirings — the algebraic foundation
- Lattices — weighted DAGs
- Path Extraction — finding optimal paths
- Layers — building correction pipelines
Working with WFST algorithms?
- WFST Operations → 2. Shortest Distance → 3. Weight Pushing → 4. Determinization → 5. Minimization
Building speech recognition?
- CTC Topologies → 2. ASR Pipeline → 3. Cascade Construction → 4. Acoustic Overview → 5. Subword Lexicon → 6. Beam Optimization → 7. GPU Acceleration
Integrating with deep learning?
- Differentiable Operations → 2. Top-Down Autograd → 3. Deep Learning Integration → 4. Weak Supervision
Exploring transducer families?
- Overview → 2. Multitape → 3. Pushdown → 4. Tree Transducers → 5. Neural Transducer
Building code-correction systems?
- Code Correction Overview → 2. Syntax Recovery → 3. Pattern-Aware → 4. Configuration