Skip to content

README.md

Latest commit

 

History

History
85 lines (73 loc) · 5.55 KB

README.md

File metadata and controls

85 lines (73 loc) · 5.55 KB
Raw

duallity documentation

Welcome to the full documentation for duallity — Levenshtein automata as lling-llang WFSTs. This hub maps the corpus and suggests reading orders. The crate-root README is the one-page overview; everything below goes deeper, from first-principles theory through the Rust architecture, per-variant design, task-oriented guides, and the engineering/security envelope.

The map

docs/
├── theory/          ← what a Levenshtein WFST is, and why (semirings, automata, composition, limits)
├── architecture/    ← how it is built (traits, state encoding, laziness, registries)
├── design/          ← one page per WFST variant (API + exact semantics + honest limits)
├── guides/          ← task-oriented usage (quickstart, choosing, composing, phonetics, tuning)
├── engineering/     ← safety, concurrency, testing
├── security/        ← threat model, hashing & collisions
├── references/      ← bibliography (with DOIs) + glossary
├── diagrams/        ← all diagram sources + rendered SVGs + the shared color legend
└── archive/         ← inherited research designs, retained verbatim, outside the shipped crate surface
Section Start here
Theory theory/README — and the master notation table every other page uses
Architecture architecture/README
Design (variants) design/README — the variant selection matrix
Guides guides/README — install + feature flags
Engineering engineering/README
Security security/README
References bibliography · glossary
Diagrams diagrams/README — catalog + color legend

Reading orders

Newcomer (≈30 min) — understand the idea and run it:

  1. crate README
  2. theory/01 · Semirings and WFSTs
  3. theory/02 · Edit distance and Levenshtein automata
  4. guides/01 · Quickstart
  5. guides/02 · Choosing a variant

Implementer (≈2 h) — integrate or extend duallity:

  1. the Newcomer path, then
  2. theory/03 · The Levenshtein automaton as a transducer and theory/04 · Composition
  3. all of architecture/
  4. the design page(s) for the variant(s) you use
  5. guides/03 · Composing pipelines and guides/05 · Performance and tuning
  6. engineering/ and security/

Researcher (≈3 h) — the full theory and provenance:

  1. all of theory/ (01 → 07), including the complete correctness proofs
  2. references/bibliography
  3. the design pages for exact semantics
  4. theory/06 · WallBreaker and theory/07 · Regular-language limits

Conventions

  • Mathematics is GitHub-flavored MathJax. Inline math is a backtick span wrapped in dollar signs — e.g. $`\oplus`$ renders $`\oplus`$ — and display math is a fenced block whose info-string is math. (A literal dollar character is written as an inline code span, `$`.) Every symbol is defined once in the master notation table; the glossary mirrors those renderings in prose. These two files plus the diagram color legend are the three single sources of truth the rest of the corpus draws from.
  • Diagrams use one shared color legend: liblevenshtein = red-pink, libdictenstein = green, duallity = blue, lling-llang = yellow, output = purple; query/input tape = orange, dictionary/output tape = teal; match/substitute/insert/delete = green/red/blue/orange; accepting = gold. Each is a committed source (PlantUML, D2, or Graphviz) plus a rendered SVG; mathematical labels are typeset with PlantUML <latex> where the illustration carries formulae.
  • ⚠ Honest limitations are flagged in the design pages where a variant departs from its ideal — e.g. the Rewrite WFST uses unconditional rules and the Pipeline builder does not itself compose or search. Nothing here over-promises.

A note on archive/

The archive/ directory holds documentation inherited from an earlier project (liblevenshtein-rust) describing a research FST + CFG + Neural text-normalization system. It sits outside duallity's shipped crate surface and is retained verbatim, under its original banners, as historical context — it is deliberately not rewritten to these conventions. The canonical, accurate documentation of what duallity actually is and does is everything outside archive/. Where a concept there maps onto real duallity code (the phonetic-regex→NFA→WFST pipeline; the regular-language expressivity limits; tropical-semiring composition), it has been re-grounded in the canonical tree and is cross-referenced from archive/README.