rev_comp
def
The reverse complement rc(s) of a string s = a_1…a_m under a complement map cm is cm(a_m)…cm(a_1).
Statement
def rev_comp {Γ : Type*} (cm : Γ → Γ) (s : List Γ) : List Γ
- Defined in
- arXiv:2611.16573, Section 2
- Verified
- 14 Nov 2026
- Axioms
- none listed
- Used by 8
- rc_substring_freeFor a complement map cm : Γ → Γ and a finite set S : Finset (List Γ), rc_substring_free cm S holds when for all x, y ∈ S with x ≠ y, x is…
- tgreedy_rc_output_sanityWith cm = id, TGREEDY-RC on {12} can output 12.
- greedy_rc_step_sanityWith cm = id, one GREEDY-RC step on {12, 23} gives {123}.
- scs_rc_optThe optimum of the Shortest Common Superstring with Reverse Complements problem: the least length of a string that contains s or rc(s) as…
- greedy_rc_stepFor cm : Γ → Γ and S, S' : Finset (List Γ), greedy_rc_step cm S S' holds when S has more than one element and, with V = S ∪ rev_comp cm ''…
- mgreedy_rc_stepFor cm : Γ → Γ and states st = (S, T), st' : Finset (List Γ) × Finset (List Γ), mgreedy_rc_step cm st st' holds when, with V = S ∪…
- rev_comp_sanityThe reverse complement of 011 under n ↦ 3 − n is 223.
- scs_rc_opt_singleton_leThe SCS-RC optimum of a single string is at most its length.
Read back from the Lean
For any type Γ, given a function cm : Γ → Γ and a list s : List Γ, rev_comp cm s is defined as the reverse of the list obtained by applying cm elementwise to s (that is, (s.map cm).reverse).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The reverse complement rc(s) of a string: reverse it and complement each letter. -/ def rev_comp {Γ : Type*} (cm : Γ → Γ) (s : List Γ) : List Γ := (s.map cm).reverse